33
44//! TurboQuant vector quantization extension type for Vortex.
55//!
6- //! Implements a Stage 1 TurboQuant encoding ([arXiv:2504.19874], [RFC 0033] ) for lossy compression
7- //! of high-dimensional vector data. The extension operates on
6+ //! Implements the TurboQuant encoding ([arXiv:2504.19874]) for lossy compression (quantization) of
7+ //! high-dimensional vector data as a lossy extension type. TurboQuant converts to and from
88//! [`Vector`](vortex_tensor::vector::Vector) extension arrays, encoding their `FixedSizeList`
9- //! storage into quantized codes after a structured orthogonal surrogate transform.
9+ //! storage into quantized codes after a random orthogonal transform (via a Structured Orthogonal
10+ //! Random Features matrix, see the `sorf` module for more information).
1011//!
1112//! [arXiv:2504.19874]: https://arxiv.org/abs/2504.19874
12- //! [RFC 0033]: https://vortex-data.github.io/rfcs/rfc/0033.html
1313//!
1414//! # Overview
1515//!
16- //! TurboQuant minimizes mean-squared reconstruction error (1-8 bits per coordinate)
17- //! using MSE-optimal scalar quantization on coordinates of a transformed unit vector.
16+ //! TurboQuant minimizes mean-squared reconstruction error (1-8 bits per coordinate) using
17+ //! MSE-optimal scalar quantization on coordinates of a transformed unit vector.
1818//!
19- //! The [`TQEncode`] scalar function first computes and stores the original L2 norm for each vector
20- //! row, then normalizes each valid nonzero row internally before SORF transform and scalar
21- //! quantization. The [`TQDecode`] scalar function dequantizes through deterministic centroids,
22- //! applies the inverse SORF transform, truncates back to the original dimension, and re-applies the
23- //! stored norm.
19+ //! Each input vector of `dimensions` coordinates is split into a fixed sequence of contiguous
20+ //! power-of-two-sized slices called **blocks**, whose widths are chosen by the user through
21+ //! [`TurboQuantConfig`] and stored verbatim in [`TurboQuantMetadata::block_sizes`]. The TurboQuant
22+ //! algorithm runs on every block independently: each block has its own stored L2 norm, its own SORF
23+ //! matrix seeded by a distinct derived seed, and its own scalar-quantization centroid table sized
24+ //! to that block's width. Block `i` covers input coordinates
25+ //! `[offset_i .. offset_i + block_sizes[i])` with `offset_i = sum(block_sizes[..i])`; a block
26+ //! extending past `dimensions` is zero-padded on encode, and the reconstructed coordinates past
27+ //! `dimensions` are dropped on decode.
2428//!
25- //! The encoded storage is a row-aligned extension tree:
29+ //! The encoded storage is a row-aligned extension tree of one outer struct holding one inner struct
30+ //! per block:
2631//!
2732//! ```text
2833//! Extension<TurboQuant>(
2934//! Struct {
30- //! norms: Primitive<element_ptype, vector_validity>,
31- //! codes: FixedSizeList<Primitive<u8>, padded_dim, vector_validity>,
35+ //! block_0: Struct {
36+ //! norms: Primitive<element_ptype, vector_validity>,
37+ //! codes: FixedSizeList<Primitive<u8>, block_sizes[0], vector_validity>,
38+ //! },
39+ //! ...
40+ //! block_{N-1}: Struct { norms: ..., codes: FixedSizeList<u8, block_sizes[N-1], ...> },
3241//! }
3342//! )
3443//! ```
3544//!
36- //! Stored norms are authoritative for future TurboQuant-aware scalar functions. Decoded quantized
37- //! directions are not guaranteed to have unit norm after scalar quantization and inverse transform.
45+ //! IMPORTANT NOTE: Stored norms are authoritative for future TurboQuant-aware scalar functions.
46+ //! Decoded quantized directions are not guaranteed to have unit norm after scalar quantization and
47+ //! inverse transform.
48+ //!
49+ //! # Limitations
50+ //!
51+ //! The current encoding is intentionally MSE-only. It does not yet implement the paper's QJL
52+ //! residual correction for unbiased inner-product estimation.
3853//!
3954//! # Source map
4055//!
4156//! Implementation details are documented next to the code that owns them:
4257//!
43- //! - `vector/storage.rs`: physical storage shape, full-length child arrays, and field-level
44- //! validity for null vectors.
45- //! - `vector/normalize.rs`: TurboQuant-local normalization and how it differs from the tensor
46- //! crate's null-row zeroing helper.
47- //! - `vector/quantize.rs`: SORF transform, centroid lookup, and why invalid rows are skipped rather
48- //! than quantized.
58+ //! - `config.rs`: the operator-facing [`TurboQuantConfig`] and its bit-width and block-list
59+ //! validation.
60+ //! - `vtable.rs`: the [`TurboQuant`] extension dtype, [`TurboQuantMetadata`] (including the
61+ //! `block_sizes` list), its proto wire format, and storage-dtype validation.
62+ //! - `scalar_fns/`: the [`TQEncode`] and [`TQDecode`] scalar functions and the metadata wire
63+ //! format glue.
64+ //! - `vector/storage.rs`: the row-aligned per-block storage layout and the outer-covers-inner
65+ //! validity coverage rules.
66+ //! - `vector/quantize.rs`: the block-aware encode pipeline (per-block norm, per-block SORF,
67+ //! scalar quantization).
4968//! - `centroids.rs`: deterministic Max-Lloyd centroid computation and process-local caching.
50- //! - `sorf/`: the Walsh-Hadamard-based structured transform and the stable SplitMix64 sign stream.
51- //!
52- //! The current encoding is intentionally MSE-only. It does not yet implement the paper's QJL
53- //! residual correction for unbiased inner-product estimation, and it still uses internal
54- //! power-of-2 padding rather than the block decomposition proposed in RFC 0033.
69+ //! - `sorf/`: the Walsh-Hadamard-based structured transform, the stable SplitMix64 sign stream,
70+ //! and the per-block seed derivation that gives each block its own SORF instance.
5571
5672mod centroids;
5773mod config;
@@ -66,11 +82,15 @@ pub use scalar_fns::TQEncode;
6682pub use vtable:: TurboQuant ;
6783pub use vtable:: TurboQuantMetadata ;
6884
69- // TODO(connor): We need to somehow make sure that callers call `vortex_tensor::initialize` first .
85+ // TODO(connor): enforce the `vortex_tensor::initialize` ordering at registration time .
7086/// Register the TurboQuant extension type with a Vortex session.
87+ ///
88+ /// Callers must register `vortex_tensor` on the session first so the `Vector` extension type that
89+ /// TurboQuant converts to and from is available.
7190pub fn initialize ( session : & vortex_session:: VortexSession ) {
7291 use vortex_array:: dtype:: session:: DTypeSessionExt ;
7392 use vortex_array:: scalar_fn:: session:: ScalarFnSessionExt ;
93+
7494 session. dtypes ( ) . register ( TurboQuant ) ;
7595
7696 session. scalar_fns ( ) . register ( TQEncode ) ;
0 commit comments