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]
