xande opened a new pull request, #15903:
URL: https://github.com/apache/lucene/pull/15903

   ## Summary
   
   This PR adds a new `FlatVectorsFormat` implementation based on the 
[TurboQuant](https://research.google/blog/turboquant-redefining-ai-efficiency-with-extreme-compression/)
 algorithm (Zandieh et al., 
[arXiv:2504.19874](https://arxiv.org/abs/2504.19874), ICLR 2026) to the 
`lucene/sandbox` module.
   
   This implementation was co-authored with an AI coding agent 
([Kiro](https://kiro.dev)) as an experiment in AI-assisted open source 
contribution. The agent handled the bulk of the code generation, test writing, 
and iterative debugging while I provided direction, reviewed outputs, ran 
benchmarks, and validated against real datasets. I want to be transparent that 
while I've tested and benchmarked this across various configurations, I don't 
have deep expertise in Lucene's codec internals - I'd greatly appreciate 
thorough review from the community.
   
   ## Motivation
   
   Current Lucene vector quantization formats (scalar quantization, BBQ) are 
limited to 1024 dimensions and require per-segment calibration. With embedding 
models increasingly producing higher-dimensional vectors (OpenAI 
text-embedding-3-large at 3072d, various 4096d models emerging), we need a 
quantization approach that scales beyond this limit.
   
   TurboQuant is a data-oblivious rotation-based quantizer that:
   - Requires **no calibration** - precomputed codebooks, each vector quantized 
independently
   - Supports **dimensions up to 16,384** (vs 1024 limit of existing formats)
   - Enables **byte-copy merge** - all segments share the same rotation seed, 
so merge never re-quantizes
   - Is **streaming-friendly** - no warmup period, no need to sample data 
upfront
   
   ## Design
   
   Follows the `Lucene104ScalarQuantizedVectorsFormat` pattern:
   
   - `TurboQuantFlatVectorsFormat extends FlatVectorsFormat` - stores quantized 
vectors in `.vetq`, metadata in `.vemtq`, delegates raw vectors to 
`Lucene99FlatVectorsFormat`
   - `TurboQuantHnswVectorsFormat extends KnnVectorsFormat` - convenience 
composition with `Lucene99HnswVectorsWriter/Reader`
   - `TurboQuantVectorsScorer implements FlatVectorsScorer` - LUT-based scoring 
directly from packed bytes
   - `TurboQuantEncoding` enum: BITS_2 (16x), BITS_3 (~10.7x), BITS_4 (8x), 
BITS_8 (4x) compression
   - Block-diagonal Hadamard rotation for non-power-of-2 dimensions (e.g., 
d=768 → blocks 512+256)
   - Placed in `lucene/sandbox` - no changes to `lucene/core`
   
   ## Implementation
   
   12 source files (2,090 lines), 11 test files (1,591 lines), 1 JMH benchmark:
   
   ```
   sandbox/codecs/turboquant/
   ├── TurboQuantEncoding.java              Enum: BITS_2/3/4/8
   ├── BetaCodebook.java                    Precomputed Lloyd-Max centroids
   ├── HadamardRotation.java                Block-diagonal FWHT + permutation + 
sign flip
   ├── TurboQuantBitPacker.java             Bit-packing for b=2,3,4,8
   ├── TurboQuantScoringUtil.java           LUT-based dot product & distance
   ├── TurboQuantFlatVectorsFormat.java     FlatVectorsFormat SPI entry point
   ├── TurboQuantFlatVectorsWriter.java     Rotate + quantize + write at flush
   ├── TurboQuantFlatVectorsReader.java     Off-heap read + scoring delegation
   ├── OffHeapTurboQuantVectorValues.java   mmap'd random access to quantized 
data
   ├── TurboQuantVectorsScorer.java         FlatVectorsScorer implementation
   ├── TurboQuantHnswVectorsFormat.java     HNSW + TurboQuant composition
   └── package-info.java                    Javadoc with format spec
   ```
   
   ## Benchmark: Cohere v3 Wikipedia English
   
   400K vectors, 1024 dimensions, dot product similarity, HNSW (maxConn=64, 
beamWidth=250), fanout=100, topK=100, 10K queries, force-merged to 1 segment.
   
   | Encoding | Compression | Recall@100 | QPS | Latency | Index time | Force 
merge | Index size |
   |---|---|---|---|---|---|---|---|
   | TurboQuant b=2 | 16x | 0.811 | 113 | 8.8ms | 75s | 924s | 1,719 MB |
   | TurboQuant b=3 | ~10.7x | 0.887 | 116 | 8.6ms | 76s | 160s | 1,767 MB |
   | TurboQuant b=4 | 8x | 0.935 | 117 | 8.5ms | 76s | 870s | 1,816 MB |
   | TurboQuant b=8 | 4x | 0.983 | 115 | 8.6ms | 81s | 126s | 2,011 MB |
   
   Note: force merge times for b=2 and b=4 are anomalously high compared to b=3 
and b=8 - this may be a caching artifact and needs further investigation.
   
   ## Test results
   
   107 dedicated TurboQuant tests pass - 3 skipped (byte-vector-only), 
TurboQuant is float32 only:
   
   | Test suite | Tests | Notes |
   |---|---|---|
   | TestTurboQuantEncoding | 7 | Wire number serialization, packed lengths |
   | TestBetaCodebook | 7 | Centroid symmetry, MSE distortion validation |
   | TestHadamardRotation | 9 | Norm/IP preservation, round-trip, 
block-diagonal quality |
   | TestTurboQuantBitPacker | 6 | Round-trip all encodings × dimensions |
   | TestTurboQuantScoringUtil | 2 | LUT vs naive agreement < 1e-5 |
   | TestTurboQuantHnswVectorsFormat | 53 | Inherited from 
BaseKnnVectorsFormatTestCase |
   | TestTurboQuantHnswVectorsFormatParams | 6 | Parameter validation, toString 
|
   | TestTurboQuantHighDim | 2 | Index + search at d=768 and d=4096 |
   | TestTurboQuantQuality | 11 | Recall, edge cases, merge stress, similarity 
matrix |
   | TestTurboQuantRecall | 5 | Recall at d=768/4096 across all encodings |
   | TestTurboQuantBruteForceRecall | 3 | Brute-force recall isolating 
quantization quality |
   
   ## JMH microbenchmarks (d=4096, b=4, single thread)
   
   ```
   Benchmark                              Mode  Cnt       Score   Units
   TurboQuantBenchmark.dotProductScoring  thrpt    2  313,617   ops/s   (~3.2 
µs/candidate)
   TurboQuantBenchmark.hadamardRotation   thrpt    2   32,125   ops/s   (~31 
µs/query)
   TurboQuantBenchmark.quantize           thrpt    2    8,169   ops/s   (~122 
µs/vector)
   ```
   
   ## What's not implemented (deferred)
   
   1. **Byte-copy merge optimization** - currently re-quantizes from raw 
vectors during merge. The architecture supports byte-copy since all segments 
share the same rotation seed.
   2. **Panama Vector API SIMD** - the LUT scorer relies on JVM 
auto-vectorization. Explicit intrinsics could improve scoring throughput.
   3. **Quantized-only mode** - raw float32 vectors are always stored alongside 
quantized data.
   
   ## When to use TurboQuant 
   TurboQuant is best suited for:
   - Workloads with shifting data distributions (no recalibration needed)
   - Merge-heavy indices (byte-copy merge advantage)
   - Streaming/online indexing
   
   ## Open questions
   
   1. **File extensions** — `.vetq` / `.vemtq` following the convention that 
different format types use different extensions. Any concerns?
   2. **Max dimensions** — `getMaxDimensions()` returns 16384. Reasonable?
   3. **Sandbox vs codecs** — placed in sandbox as this is a new, 
community-unvetted contribution. Should it move to codecs once stabilized?


-- 
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]

Reply via email to