Skip to content

Commit 6396469

Browse files
committed
test(vortex-turboquant): block-decomposition coverage and docs
Migrate the suite to the block layout and add round-trip, fidelity (per-block and whole-vector MSE), seed-distinctness, multi-block null/zero-norm, malformed-metadata/code/norm, and NaN/Inf coverage. Refresh the crate docs and add a multi-block file round-trip. Signed-off-by: Connor Tsui <[email protected]> Signed-off-by: Connor Tsui <[email protected]>
1 parent b3e4bec commit 6396469

10 files changed

Lines changed: 815 additions & 249 deletions

File tree

‎vortex-turboquant/benches/encode_decode.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,9 +4,9 @@
44
//! Benchmarks for `turboquant_encode` and `turboquant_decode` across different validity-mask
55
//! shapes.
66
//!
7-
//! The four mask shapes (`AllTrue`, `AllFalse`, dense `Values`, sparse `Values`) exercise the
8-
//! variant-specialized paths added in the mask refactor in `vector/normalize.rs`,
9-
//! `vector/quantize.rs`, and `scalar_fns/decode.rs`.
7+
//! The four mask shapes (`AllTrue`, `AllFalse`, dense `Values`, sparse `Values`) exercise both
8+
//! the encoder's per-row mask dispatch in `vector/quantize.rs` and the variant-specialized mask
9+
//! arms in `scalar_fns/decode.rs`.
1010
1111
#![expect(clippy::unwrap_used)]
1212

@@ -118,7 +118,7 @@ fn decode(encoded: ArrayRef, ctx: &mut ExecutionCtx) -> ArrayRef {
118118

119119
fn config() -> TurboQuantConfig {
120120
// 4 bits, 4 SORF rounds, fixed seed: representative defaults from the test fixtures.
121-
TurboQuantConfig::try_new(4, 0xDEADBEEF, 4).unwrap()
121+
TurboQuantConfig::try_new(4, 0xDEADBEEF, 4, None).unwrap()
122122
}
123123

124124
#[divan::bench(args = MASK_SHAPES)]

‎vortex-turboquant/src/lib.rs‎

Lines changed: 48 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -3,55 +3,71 @@
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
5672
mod centroids;
5773
mod config;
@@ -66,11 +82,15 @@ pub use scalar_fns::TQEncode;
6682
pub use vtable::TurboQuant;
6783
pub 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.
7190
pub 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

Comments
 (0)