RKSPD opened a new pull request, #16709:
URL: https://github.com/apache/lucene/pull/16709
# SegmentIVF: a fast(er) Lucene-native inverted-file vector codec
SegmentIVF is a Lucene KNN codec designed to make vector search behave like
Lucene full-text search architecture. It is a further development of IVFaster
#16567 with some cool new features. Before going into the implementation, it is
important to describe the architectural philosophy behind the codec and the
restrictions that make traditional vector indexes difficult to use inside
Lucene.
Lucene's segment architecture gives us a simple concurrency model, immutable
files after flush, natural near-real-time publication, and straightforward
distribution across nodes. Vector search methods are often at odds with this
model. Graph structures such as HNSW must be rebuilt during segment merges,
while traditional k-means IVF implementations can impose a large independent
training cost on every new segment. Quantizers trained from segment-local data
also require full-precision vectors to survive so that every merge can train a
new quantizer and encode the vectors again.
SegmentIVF starts from the opposite constraint: a vector's code must remain
valid regardless of which segment holds it. Flushes and merges should reuse
earlier clustering work, merging should copy existing encoded rows instead of
returning to float32, and search work should scale with the documents searched
rather than multiplying expensive reranking by the number of segments.
## Benchmark
This benchmark uses 1M Cohere Embed multilingual-v3 Wikipedia-en vectors,
dimension 1024, unit-normalized with dot-product similarity, and 1,000 held-out
queries. Recall is recall@100 against exact nearest neighbors. The index was
force-merged to one segment. The machine is a 64-core Arm server
`m7g.16xlarge`with 256-bit SVE running Corretto 25.0.4. Search latency is warm,
single-threaded, and the minimum of three independent JVM runs through
luceneutil.
SegmentIVF uses its defaults: `nlist=1000` (`sqrt(1M)`), `nprobe=32`,
`spillBits=1`, `spillMargin=1.05`, a `0.75` adaptive probe margin, Nitrox2
coarse codes, INT8 fine codes, and a global rerank of `max(100, 7 * k)`
candidates. Recall is dialed with `nprobe` alone.
The Lucene HNSW measurements below are the numbers from the previous
benchmark on this dataset and machine. They use Lucene's 7-bit scalar-quantized
HNSW path with a Lucene99 graph, `M=16`, and `beamWidth = 100`.
| Recall band | SegmentIVF | Lucene HNSW SQ 7-bit | Speedup |
| --- | ---: | ---: | ---: |
| ~0.89 | 0.886 @ 0.465 ms (`nprobe=10`) | 0.888 @ 0.918 ms (`fanout=0`) |
2.0x |
| ~0.91 | 0.911 @ 0.527 ms (`nprobe=14`) | 0.908 @ 1.109 ms (`fanout=25`) |
2.1x |
| ~0.92 | 0.925 @ 0.576 ms (`nprobe=18`) | 0.923 @ 1.254 ms (`fanout=50`) |
2.2x |
| ~0.94 | 0.943 @ 0.676 ms (`nprobe=28`) | 0.939 @ 1.584 ms (`fanout=100`) |
2.3x |
| ~0.95 | 0.955 @ 0.816 ms (`nprobe=48`) | 0.956 @ 2.141 ms (`fanout=200`) |
2.6x |
| ~0.96 | 0.960 @ 1.033 ms (`nprobe=128`) | 0.963 @ 2.779 ms (`fanout=300`)
| 2.7x |
### Indexing
| Codec | Index build | Force merge to one segment | Index size |
| --- | ---: | ---: | ---: |
| SegmentIVF | 17.488 s | 13.794 s | 1906.70 MB |
| Lucene HNSW SQ 7-bit | 150.3 s | 113.8 s | 4965 MB |
SegmentIVF builds the initial index 8.6x faster, force-merges 8.3x faster,
and produces an index 61.6% smaller. The median end-to-end time to the final
one-segment index was 31.575 seconds, compared with 264.1 seconds for the
previous HNSW measurement, an 8.4x improvement.
The size comparison needs one qualification because the indexes retain
different data. Lucene's scalar-quantized HNSW format wraps a raw float32
delegate so that vectors can be requantized during merge. Most of its 4965 MB
is therefore full-precision vector data. SegmentIVF keeps no float32 copy of
each document vector. Its fine representation is one signed byte per dimension
plus a per-vector scale, and its coarse representation is a 2-bit Nitrox2 code.
Spill copies those compressed records only for vectors close enough to a cell
boundary.
The indexing speed comes from the same architectural choice. SegmentIVF has
no document graph to rebuild. Build rows are staged sequentially on disk,
encoding and clustering use all available build workers, compatible merges copy
existing fine and coarse codes, and HotStart carries useful centroid and
assignment state into the next clustering run.
### 900M-vector scaling (on a single `m7g.16xlarge` )
This run indexed the first 900M vectors from a 901,180,094-vector FineWeb
corpus. The vectors are 768-dimensional FP16 input with cosine similarity. The
codec used `nlist=3873`, which is approximately `sqrt(15M)` for the target
maximum segment population, `spillBits=1`, `spillMargin=1.05`, and the INT8
fine tier.
| Documents | Indexing time | Final merge drain | End-to-end | End-to-end
throughput | Final segments | Index size |
| ---: | ---: | ---: | ---: | ---: | ---: | ---: |
| 900,000,000 | 36,970.572 s | 156.123 s | 37,126.695 s | 24,241 vectors/s |
104 | 1.528 TiB |
SegmentIVF is designed to scale. The complete build took **10 hours 18
minutes 47 seconds**, including waiting for already-running background merges
at the end. It was not force-merged: the result is a normal Lucene index with
104 immutable segments averaging 8.65M vectors each. Background merges ran
concurrently with ingestion; the separate 156-second figure is only the final
drain after the last document was committed.
## Global, segment-independent codes
Quantization is critical ANN infrastructure: it reduces storage and memory
traffic while retaining production-quality recall. In Lucene, quantizer design
also determines merge behavior.
SegmentIVF's transform and encodings do not depend on segment statistics.
Every vector is L2-normalized and rotated by
```
R = F · P · S
```
where `S` applies deterministic random plus/minus-one signs, `P` is a
Fisher-Yates permutation, and `F` is a normalized fast Walsh-Hadamard transform
applied block-diagonally over the set bits of the dimension. The seed is
derived from the dimension, so every segment for a compatible field uses the
same rotation.
The rotation spreads variance across dimensions, preserves similarity, and
puts unit vectors on a shared grid whose coordinate scale is determined by the
dimension rather than by a training set. The INT8 fine code then uses a
per-vector scale, and the Nitrox2 coarse code uses fixed thresholds derived
from `1 / sqrt(dim)`. Moving a vector between segments does not change either
code.
This gives merges ordinary Lucene semantics: copy the encoded row, update
its document and cell metadata, and place it in the new posting lists. There is
no segment-level requantization pass and no need to retain the original float32
vector.
## Nitrox2: A quantizer built for vector search
The coarse tier has a narrower job than the fine tier. It does not need to
produce the final ranking; it only needs to keep true neighbors in a bounded
shortlist. That permits a much cheaper representation.
Nitrox2 stores two threshold planes for every rotated coordinate. At
dimension `d`, the thresholds are `-0.5 / sqrt(d)` and `+0.5 / sqrt(d)`,
producing three ordered levels. Because the planes are cumulative, Hamming
distance between two codes is the sum of the per-coordinate level differences:
```
popcount(query_plane_0 XOR doc_plane_0)
+ popcount(query_plane_1 XOR doc_plane_1)
```
The query and document use the same code. There is no document correction
term and no asymmetric expression that a scan path can accidentally omit. At
1024 dimensions the complete coarse code is 256 bytes.
The scan kernel is a fused XOR and popcount over contiguous rows. The Panama
Vector API implementation processes native memory directly, scores several rows
together so query chunks are reused, and falls back to scalar Java when the
vector module is unavailable. The result is a bandwidth-oriented posting-list
scan with no native library dependency.
The fine tier defaults to INT8. Each rotated vector uses one signed byte per
dimension and one scale. The query is encoded once, and reranking uses SIMD
byte dot products before applying Lucene's similarity-score transformation.
FP32 is also supported when a caller prefers exact fine records over the
smaller default.
## Indexing: Segment-aware clustering and HotStart
### How cold segment build works:
1. Normalize, rotate, and encode every vector into a disk-backed staging
file.
2. Seed `nlist` centroids from a deterministic reservoir sample.
3. Route each vector to its nearest centroid.
4. Update the spherical centroids from their assigned vectors.
5. Reroute only vectors whose assignment may have changed.
6. Repeat until fewer than 0.5% of vectors move or ten Lloyd iterations
complete.
7. Assign eligible boundary vectors to one additional SOAR-selected cell.
8. Write contiguous posting runs and build the centroid graph.
The expensive mistake in a segment architecture is treating every flush and
merge as an unrelated clustering problem. `Clustering.HotStart` retains recent
clustering state and reuses it in two places.
For a flush, SegmentIVF finds the largest live compatible segment written by
this process. Its centroids seed the new segment, and compatible segments from
the same lineage contribute membership-weighted centroid state. This makes a
stream of near-real-time flushes progressively warmer instead of repeatedly
paying the full cold-start cost.
For a merge, SegmentIVF selects the largest compatible source segment as the
donor. Its centroid layout seeds the merged segment. Sources from the same
HotStart lineage contribute their live primary-cell populations to a weighted
seed, and their rows carry primary and runner-up assignments into the first
iteration. Rows whose lineage or assignment is unknown are safely routed from
scratch.
### Exact movement pruning
Rerouting every vector after every centroid update is mostly wasted work
because only vectors near a Voronoi boundary can change assignment. SegmentIVF
tracks the best and runner-up centroids for each vector and accumulates the
movement of those centroids.
A vector can only keep its current assignment when
```
d2 - d1 > movement(c1) + movement(c2)
```
where `d1` and `d2` are the distances to its current best and runner-up
cells. When the runner-up is not known, the implementation uses a conservative
bound derived from the maximum centroid movement. This is a sufficient
condition, so skipped vectors cannot have changed their nearest cell.
The bound follows the k-means pruning line from Elkan, Hamerly, and Yinyang,
applied here to donor-warm-started segment clustering. As centroids settle,
almost all vectors stop participating in later routing passes.
## Indexing: Spill
Traditional IVF probes the cells whose centroids are closest to the query.
In high dimensions, pairwise distances concentrate and cell boundaries become
unreliable: a true neighbor can sit just across a Voronoi boundary in a cell
that is not among the query's first probes.
Spill attacks that failure directly. A vector close to a boundary is written
to its primary cell and `spillBits` secondary cells, so a query can find it
from either side. The default `spillBits=1` permits one secondary copy, and
`spillMargin=1.05` limits duplication to vectors whose two closest cells are
competitive within the margin.
The secondary cell is selected with SOAR, Spilling with
Orthogonality-Amplified Residuals. Choosing the second-nearest centroid often
duplicates the same failure direction as the primary. SOAR instead penalizes a
candidate whose residual is parallel to the primary residual:
```
loss(c) = ||v - c||² + lambda * (r1 · (v - c))² / ||r1||²
where r1 = v - c_primary
```
The default `lambda=1` favors a complementary cell whose residual covers a
different direction. That makes each spill copy more useful and lets the codec
keep the spill count and index size low.
Spill means one document may appear in several probed posting lists. A fixed
slot shortlist can therefore collapse to far fewer distinct documents.
SegmentIVF admits up to `shortlist * (1 + spillBits)` slots, orders them by
coarse distance, deduplicates by document, and keeps the requested number of
distinct candidates. The writer's spill cap consequently gives the reader a
hard bound on how much extra admission is needed.
## Search: Query-Time Cell selection
Choosing the cells to scan is itself a nearest-neighbor problem. A
brute-force scan across all `nlist` centroids is reasonable while indexing
because many documents can share a tiled, cache-resident centroid scan. A
single search query cannot amortize that work, and `nlist` must grow with the
corpus to keep posting lists small.
SegmentIVF therefore builds a compact graph over centroid codes. Each node
stores the centroid's 2-bit Nitrox2 code next to up to 16 neighbor ordinals in
a cache-aligned record inspired by USearch. At dimension 1024 the code is 256
bytes instead of the centroid's 4096-byte float32 vector.
The query starts with a maximum `nprobe`, then applies an adaptive margin to
the exactly ranked centroid candidates. A cell is discarded once its centroid
distance exceeds the configured fraction of the best cell's distance. Easy
queries with one dominant cell stop early; ambiguous queries retain more cells.
The default margin is `0.75`, and a margin of `1.0` disables the cutoff.
## Search: Index-wide rerank
Lucene searches segments independently, which creates a cost for a two-tier
vector index. If every segment fine-reranks its own fixed shortlist, fine
scoring and random fine-record reads grow linearly with the number of segments.
That is especially undesirable for near-real-time indexes, where segment count
is expected to fluctuate.
### How `SegmentIVFKnnQuery` works:
1. Normalize and rotate the query once for each segment search.
2. Encode the Nitrox2 and fine query representations once for that search.
3. Select cells and scan contiguous Nitrox2 posting runs in each segment.
4. Produce a deduplicated coarse shortlist from each segment.
5. Merge all leaf shortlists by coarse distance.
6. Keep one index-wide budget of `max(100, 7 * k)` candidates.
7. Read and fine-rerank only those records, in parallel across the leaves
that contributed them.
For a top-100 query, the entire index fine-reranks 700 records whether it
has one segment or many. A plain `KnnFloatVectorQuery` remains supported
through the codec interface, but it performs the normal per-segment rerank.
`SegmentIVFKnnQuery` is the path that provides the index-wide bound.
Note: 7 * k was chosen empirically using Cohere Wikipedia v3-1024 and may
not be optimal for your dataset.
## Search: Automatic mapped reads and io_uring
The coarse and fine tiers have different memory access patterns, so
SegmentIVF manages them differently.
Coarse posting runs are large, contiguous, and scanned repeatedly. On reader
open, SegmentIVF queues a background off-heap copy of the coarse codes and
slot-to-document mapping when the memory budget allows it. At most three
quarters of that remaining space is reserved for pinned coarse data. Searches
never wait for the copy; they use the mapped view until the pinned copy is
published.
Fine records are accessed sparsely after the global shortlist is known.
Mapped reads are fastest while the working set fits in memory, but a page miss
turns each scattered record into a synchronous fault. SegmentIVF tracks the
total fine-tier bytes across open readers and reevaluates its read path at most
once per second:
- Use mapped records while the fine tiers fit in the memory left after the
heap and pinned coarse data.
- Switch to io_uring when the fine tiers exceed that room or Linux PSI
reports sustained memory pressure.
- Use hysteresis, switching on above 1% `some avg10` pressure and back below
0.1%, to avoid oscillation.
The io_uring path submits the rerank's scattered fine-record reads as one
batch. Cached records still come from the page cache, while page misses can run
concurrently instead of serializing as faults on the search thread. Rings and
buffers are per search thread; each segment reader owns only its file
descriptor. If io_uring is unavailable or a batch fails, the reader falls back
to the mapped input.
| Memory limit | Automatic mode | Forced mmap | Forced buffered io_uring |
Path selected automatically |
|---:|---:|---:|---:|---|
| Unlimited, warm | 0.728–0.747 ms | 0.726–0.728 ms | 1.292–1.303 ms | mmap |
| 3.0 GB | 0.717–0.729 ms | 0.720–0.723 ms | 1.324–1.342 ms | mmap |
| 1.6 GB | 4.802–4.803 ms | 9.846–10.054 ms | 4.807–4.812 ms | io_uring |
| 1.1 GB | 9.407–9.418 ms | 32.304–32.314 ms | 9.406–9.418 ms | io_uring |
## Filtered search
Filters are applied before vector scoring. `SegmentIVFKnnQuery` materializes
a dense filter as a per-segment bit set and passes it into the codec.
The reader chooses between two paths based on filter cost:
- For a selective filter, visit accepted documents directly and rerank their
slots.
- For a denser filter, select cells, scan only matching rows, and widen the
probe budget as selectivity falls.
Segments whose slots fit within the coarse admission pool scan all slots
instead of spending probes on mostly empty cells. Sufficiently selective
filters visit their accepted documents directly. Filtered candidates enter the
same coarse ordering and global rerank as unfiltered candidates, preserving the
index-wide fine-read bound.
## Final Note
Hi everyone, this PR is a culmination of a lot of trial and error and a
collaborative effort between many people. Thank you for reading this very long
PR description. I would appreciate any feedback on the method or general
thoughts of this IVF implementation in Lucene.
--
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]
