RKSPD opened a new pull request, #16567: URL: https://github.com/apache/lucene/pull/16567
# IVFaster: a segment-lifecycle-aware IVF vector codec (sandbox) It's no secret that vector search sits awkwardly on Lucene's segment model. Segments are immutable and merge constantly, and both properties are cheap for an inverted index and expensive for an ANN structure. There have been attempts to improve this behavior, namely `IncrementalHnswGraphMerger`, which adopts the largest incoming graph as a base and inserts the remaining documents instead of rebuilding a new graph from the document contents of both segments. However, HNSW construction itself is a very expensive operation: every inserted document is a beam search with a random access per hop, and insertion mutates the base graph's neighbor lists. Furthermore, with incremental merges, a base graph with more than 40% deletions is declined, because its connectivity has degraded, and the merge falls back to a full rebuild. All of these problems are made worse with quantization. Since standard quantization schemes create segment-dependent compressed vectors, the codec needs to keep full- precision vectors on disk just to requantize on merge. Related discussion: apache/lucene#15612. IVFaster takes the position that a vector index should look like a posting list, and is built around the Lucene segment architecture rather than adapted to it afterwards. Read literally, that is what the IVF family already is: a cell id is a key, and the vectors routed to it are the values under that key. In IVFaster, a single document also can live in multiple cells. Document vectors near a cell boundary are listed under several keys so that a query probing any one of them finds the document, with `spillBits` setting how many extra cells a document may occupy. **The structure a merge settles is `nlist`-sized, not N-sized.** The largest incoming segment donates its centroids, the other segments' documents are routed into them by a tiled scan over centroid codes, and a few Lloyd iterations settle the means. The only thing rebuilt from scratch is the centroid graph, over `nlist` nodes rather than N: in the benchmarks below, 8000 centroids against 1M documents. **Quantization is global.** The grid is derived in closed form from `dim` after a shared Hadamard rotation, with no trained or per-segment statistic, so a document's code is the same in every segment. Merges copy codes, and the codec never has to retain float32 vectors just to requantize later. Two tiers: a 2-bit coarse code quantizer (Nitrox2) narrows each probed cell to a shortlist with one XOR+popcount pass over a contiguous byte string, and an int8 fine tier ranks the survivors. Cells are chosen by greedy descent over a navigable small-world graph on the centroids. Each node's payload in the graph is the centroid's 2-bit code interleaved with its neighbor list, so a hop stays L3-resident and descent cost is set by `ef` rather than by `nlist`. **The codec is capable of disk-based search.** Slots are grouped by cell, so the byte range of every probed cell is known before the scan begins, and the reader hints all `nprobe` runs through `IndexInput#prefetch` up front, so cold faults overlap in place of one synchronous fault per cell. A graph descent has no equivalent, because the next hop's address is unknown until the current node is scored, which makes its misses serial by construction. The hint is adaptive and collapses to a counter increment once pages are resident, so it is on by default. Note: an async or batched I/O path is deliberately absent, because it only benefits when nearly everything is cold and carries heavy overhead when warm. Every number below is page-cache warm, and disk-resident performance is coming soon. ## Results 1M Cohere Embed multilingual-v3 Wikipedia-en, dim 1024, unit norm, dot product, 1000 held-out queries, recall@100 against exact NN, force-merged to one segment. Graviton3, Corretto 25, index on standard gp2 EBS (250MiB/s). Latency is warm and single-threaded through `luceneutil`. IVFaster dialed with `nprobe` and `nlist=8000`, HNSW with search fanout. Every number below was measured in one session on one machine. | recall | IVFaster `spillBits=3` | IVFaster `spillBits=2` | Lucene HNSW (SQ 7-bit) | speedup | |---|---|---|---|---| | ~0.91 | **0.911 @ 0.593 ms** (np 16) | 0.913 @ 0.607 ms (np 24) | 0.910 @ 1.122 ms (fo 25) | 1.9x | | ~0.94 | **0.938 @ 0.632 ms** (np 24) | 0.943 @ 0.712 ms (np 40) | 0.941 @ 1.600 ms (fo 100) | 2.5x | | ~0.95 | **0.951 @ 0.713 ms** (np 32) | 0.950 @ 0.778 ms (np 48) | 0.956 @ 2.189 ms (fo 200) | 3.1x | | ~0.96 | **0.960 @ 0.790 ms** (np 40) | 0.960 @ 0.902 ms (np 64) | 0.963 @ 2.817 ms (fo 300) | 3.6x | | ~0.97 | **0.972 @ 1.008 ms** (np 64) | 0.970 @ 1.155 ms (np 96) | 0.972 @ 5.103 ms (fo 800) | 5.1x | The gap widens with recall, because HNSW buys recall by visiting more nodes at a memory latency each while IVFaster scans more cells sequentially. | config | index(s) | force_merge(s) | total(s) | size (MB) | |---|---|---|---|---| | **IVFaster** `spillBits=3` | 48.3 | 50.0 | **98.3** | 5168 | | **IVFaster** `spillBits=2` | 39.8 | 42.7 | **82.6** | **3887** | | Lucene HNSW SQ 7-bit | 149.4 | 114.0 | 263.4 | 4965 | Build is storage-bound on EBS rather than CPU-bound: about half the IVFaster build wall clock is `fsync` on the data file with the cores idle, so these figures track bytes written more than clustering work. Index size is the column IVFaster loses at `spillBits=3`. A slot costs 1344 B and both the fine records and the coarse planes replicate per slot, so at `spillMargin=1.40` the index holds almost exactly four slots per document. `spillBits=2` trades that back: 25% smaller, 16% faster to build, and roughly 1.5x the `nprobe` to match a given recall, which costs 9 to 15% more latency in the 0.94-and-above bands. IVFaster config: `nlist=8000`, `spillMargin=1.40`, `soarLambda=1.0`, `lloydIters=10`, `bruteN=700`, `nprobeMargin=0.75`, `verifyMultiplier=2`, Nitrox2 coarse + int8 fine. All codec defaults except `nlist`, whose default is 1000; `nlist` is corpus-dependent and not auto-scaled, and we see best results near 100-150 docs per cell. HNSW baseline: `Lucene104HnswScalarQuantizedVectorsFormat`, 7-bit scalar quantization, `M=16`, `beamWidth=100`, dialed with search fanout. Caveats: each point is a single run and latency noise is about 5%. ## Scope Hi all. This is a sandbox codec, marked `@lucene.experimental` with no back-compat guarantee. It is a pretty big PR with 37 files under `lucene/sandbox`. It is self-contained with no other modifications to Lucene. I would really appreciate any feedback from the community. Thank you. -- 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]
