RKSPD opened a new pull request, #16683: URL: https://github.com/apache/lucene/pull/16683
### Description IVFasterEvo is a smaller successor to [IVFaster (#16567)](https://github.com/apache/lucene/pull/16567), built around the same segment-lifecycle invariants: document encodings survive changes in centroid placement, compatible merges copy encoded records without requantizing, and the graph is over centroids rather than documents. This draft adds the codec to `lucene/sandbox`, with hot initialization for flushes and merges, a custom filtered kNN query that uses Lucene's bulk scoring path, and selectivity-based probe widening. The main improvement is construction cost. In the local 1M-vector benchmark series below, IVFasterEvo builds and force-merges in roughly 153–199 seconds, versus 402 seconds for IVFaster. The timings depend on the commit/flush schedule; the controlled hot-init comparison is shown separately. These are preliminary measurements, not a claim that every workload sees the same speedup. ### Hot initialization and construction A flush starts from the largest compatible segment's centroids in the latest published commit. Seeds are scoped by index, field name, dimension and similarity; uncommitted/NRT segments do not become seed sources. Snapshots copy the centroids and retain no readers or file handles. A new index falls back to cold initialization. A merge inherits centroids and surviving primary assignments from the largest eligible input, measured by live vector count. Document mappings account for deletions and index sorting. Refinement updates primary assignments and means, and boundary spill is added afterwards using SOAR with lambda fixed at 1. Spill copies never train the means. Construction stages each document's coarse and fine records once on disk. With U8 fine records, Lloyd refinement reads the reconstructed vectors directly in rotated space and reuses the stored coarse codes. It shortlists centroids with Nitrox2, verifies candidates in floating point, and uses an own-pair movement bound to skip work. The graph is rebuilt over the centroids, not over all documents. The lifecycle invariants are preserved, but clustering remains approximate: the centroid shortlist can omit the global nearest centroid, and the own-pair bound does not certify that a third centroid cannot overtake a skipped assignment. It is not an exhaustive-Lloyd equivalence guarantee. ### Filtered search through the bulk scorer `IVFasterEvoKnnQuery` combines the supplied filter with vector-field existence and resolves multi-clause filters through their `BulkScorer`. For eligible dense conjunctions, this lets Lucene use `DenseConjunctionBulkScorer` to intersect clauses in bit-set windows. It uses the existing scoring API; no core visibility change or new core scorer is needed. The query passes the resolved bit set and its cardinality to the codec without another copy. Filters that rewrite to one clause use the stock `KnnFloatVectorQuery` path. When at most `k` documents match, the custom path scores those matches exactly. The reader checks acceptance before coarse scoring and widens the requested probe count according to filter selectivity: ```text s = min(1, acceptedCount / vectorCount) probes = min(numCentroids, ceil(baseProbes / max(s, 1/8))) ``` Thus a 25%-selective filter requests 4× as many cells, and widening is capped at 8×. This compensates for the smaller number of admissible vectors in each cell. It is a recall/latency tradeoff rather than a recall guarantee, particularly when a filter is correlated with vector clusters. ### Encoding, layout and search Nitrox2 supplies the coarse tier: a deterministic Hadamard rotation followed by two thermometer bit planes. The fine tier is either U8, using Lucene's per-vector optimized scalar quantization, or FP32. U8 bounds are per-vector; neither tier depends on segment statistics or centroid placement. Compatible merges preserve both encoded records byte-for-byte. U8 mode retains no separate FP32 document-vector copy; FP32 remains an explicit fine-tier option. Coarse and fine records occupy separate cell-ordered sections with matching slots. Spill duplicates records in both sections. Search navigates a single-layer centroid graph, ranks visited centroids by exact distance, scans selected cells in blocks, and uses a thresholded Hamming histogram to keep the best `max(700, k)` distinct coarse candidates for fine reranking. Both selected coarse runs and shortlisted fine records receive `IndexInput.prefetch` hints. SIMD kernels have scalar fallbacks. ### Preliminary results Local Apple Silicon laptop, 16 GB RAM, SSD, JDK 25 with the Vector API. Dataset: 1M Cohere multilingual-v3 Wikipedia-en vectors, 1024 dimensions, dot product, 1,000 queries, recall@100 against exact FP32 neighbors, force-merged to one segment. Settings: 1,000 centroids, one extra spill cell, spill margin 1.05, coarse shortlist 700. Evo uses U8 fine records; the IVFaster baseline is commit `5eb78a006d` and uses its int8 fine tier. | Build configuration | Index (s) | Force-merge (s) | Total (s) | |---|---:|---:|---:| | IVFaster baseline | 191.67 | 210.79 | 402.46 | | Evo, final filtered-search build | 116.49 | 82.78 | 199.27 | | Evo, flush every 125k docs, no intermediate commits | 93.60 | 78.70 | 172.30 | | Evo, commit every 125k docs, hot init enabled | 72.16 | 81.13 | 153.29 | The last two rows use the same segment-cut schedule to isolate committed-seed reuse. Hot init reduced indexing time by 23% and total build time by 11%; recall@100 at 32 probes was 0.95892 versus 0.95888. The comparison with IVFaster is across the benchmark series, not a controlled isolation of hot init alone. Each build was measured once. The unfiltered search sweep after graph and scan improvements measured: | Probes | Evo recall@100 | IVFaster recall@100 | Evo CPU ms/query | IVFaster CPU ms/query | |---|---:|---:|---:|---:| | 16 | 0.9269 | 0.9222 | 0.60 | 0.56 | | 32 | 0.9588 | 0.9535 | 0.88 | 0.82 | | 56 | 0.9716 | 0.9684 | 1.23 | 1.23 | | 96 | 0.9777 | 0.9761 | 1.79 | 1.85 | For a two-clause filter matching approximately 25% of documents, at 32 base probes, the filtered experiment measured 0.98339 recall with either query path. Using the custom bulk-scoring query reduced CPU time from 7.611 to 3.865 ms/query. Without selectivity widening, Evo measured 0.94798 recall and 5.346 ms/query; widening buys recall, while bulk filter resolution reduces the conjunction cost. Search timings are medians of three interleaved runs, each in a fresh JVM with the index warmed into the page cache. The unfiltered sweep predates the final query-wrapper pass; these are development-series results from frozen benchmark jars, not a fresh benchmark of this PR head. Equal spill-margin values also do not imply identical spill membership across the two codecs. No cold-storage performance claim is made. Measurements come from the local `lucene-quantized/benchmarks/1m-consolidated/` archive: `RESULTS.md`, `results-scan.json`, `results-filter.json`, `results-hot.json`, and their drivers/logs. That archive is not included in this code-only PR. ### Scope and validation This draft contains `3721bf32a3485533d919548482bc4e9be655182f` plus `bd22fb5ae619210818aa8d4b5b85f60308136a23`, which adds a cross-field hot-start isolation test. All 20 changed files are under `lucene/sandbox`, including SPI/module registration and build checks for Vector API references. The codec is experimental and has no compatibility guarantee with earlier experimental formats. Coverage includes committed-only seed reuse, restart/rollback and field isolation, donor assignments through deletes and sorting, quantized hot starts, byte-preserving merges, spill, filtered shortlist behavior, probe widening, dense filters across scoring windows, SIMD/scalar parity and staging-file cleanup. Validated at `bd22fb5ae619210818aa8d4b5b85f60308136a23` in a clean detached worktree with JDK 25: **44 codec tests passed**, along with sandbox forbidden-API checks, ECJ lint and Google Java Format. Test seed: `99A780568A22327B`. ```sh ./gradlew :lucene:sandbox:test \ --tests 'org.apache.lucene.sandbox.codecs.ivfaster_evo.*' \ :lucene:sandbox:forbiddenApis \ :lucene:sandbox:ecjLint \ :lucene:sandbox:checkGoogleJavaFormat ``` Feedback on the lifecycle integration, filtered-query API and construction/search tradeoffs would be especially useful. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
