SpectorQuant: Rotational Vector Quantization via Fast Walsh-Hadamard Transform
High-dimensional vector embeddings are computationally expensive to store, index, and search. Quantization compresses these vectors (e.g., from 32-bit floats to 8-bit integers), but standard scalar quantization suffers from severe precision loss when embeddings contain outlier dimensions with disproportionately large values.
Spector resolves this using Spector Vector-Aligned Scalar Quantization (SVASQ).
The Outlier Problem in Embedding Spaces
Modern transformer models generate embeddings where a few dimensions carry massive variance, while the remaining dimensions contain very small values. Standard INT8 quantization maps coordinates linearly:
\[x_{quantized} = \text{round}\left(255 \times \frac{x - x_{min}}{x_{max} - x_{min}}\right)\]
If \(x_{max} - x_{min}\) is dominated by an outlier dimension, the resolution for all other dimensions drops, resulting in high quantization noise. When calculating similarity, this noise corrupts cosine distance metrics, dragging down vector recall.
The SVASQ Rotation Pipeline
SVASQ solves this by rotating the vector space before applying quantization. This rotation is an orthogonal transform, meaning it preserves all pairwise Euclidean distances and angles. However, it spreads the variance of outlier dimensions uniformly across all vector lanes.
[Raw Embedding] -> [Fast Walsh-Hadamard Transform] -> [Uniform Variance] -> [INT8 Quantization]
The Math: Fast Walsh-Hadamard Transform (FWHT)
The Walsh-Hadamard matrix \(H_N\) is defined recursively for a power of two \(N\):
\[H_2 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \quad H_{2k} = H_2 \otimes H_k\]
Applying the FWHT to an embedding \(x\) computes:
\[x_{rotated} = \frac{1}{\sqrt{N}} H_N x\]
This multiplication takes \(O(N \log N)\) operations instead of the general matrix multiplication cost of \(O(N^2)\). Once rotated, the outlier values are dissipated across the entire vector. Standard linear scalar quantization is then applied to \(x_{rotated}\) to map each coordinate to an signed INT8 integer, preserving retrieval accuracy with a 4x reduction in memory footprints.
Quantization Mechanics and De-quantization
During search operations, the query vector is also rotated using the FWHT. The similarity is computed in the quantized space, and the score is de-quantized by applying a scaling factor:
\[S_{dequantized} = S_{quantized} \times \frac{\text{scale}_{query} \times \text{scale}_{candidate}}{255^2}\]
This approach ensures microsecond-level retrieval with near-zero precision degradation compared to FP32 embeddings, making Spector extremely fast and highly memory-efficient.