TurboQuant

TurboQuant_mse

TurboQuant_mse is the version of the algorithm optimized for mean-squared error. For a unit vector ${\displaystyle x\in S^{d-1}}$, the algorithm first applies a random rotation matrix ${\displaystyle \Pi \in \mathbb {R} ^{d\times d}}$ and sets ${\displaystyle z=\Pi x}$. Each coordinate of the rotated vector follows a shifted and scaled beta distribution, which converges to a normal distribution in high dimensions. In high dimensions, distinct coordinates also become nearly independent, allowing the algorithm to apply scalar quantizers independently to each coordinate.^[1]

The scalar quantizer is constructed by solving a one-dimensional continuous k-means or Lloyd–Max quantization problem. If the centroids are ${\displaystyle c_{1},c_{2},\ldots ,c_{2^{b}}}$, the quantization step stores, for each coordinate, $${\displaystyle \mathrm {idx} _{j}=\operatorname {*} {arg\,min}_{k\in [2^{b}]}|z_{j}-c_{k}|.}$$

During dequantization, the stored index for each coordinate is replaced by the corresponding centroid, giving a reconstructed rotated vector ${\displaystyle {\tilde {z}}}$. The algorithm then rotates back:^[1] $${\displaystyle {\tilde {x}}=\Pi ^{\top }{\tilde {z}}.}$$

The paper gives the following bound for TurboQuant_mse: $${\displaystyle D_{\mathrm {mse} }\leq {\frac {\sqrt {3\pi }}{2}}\cdot {\frac {1}{4^{b}}}.}$$ It also reports finer-grained MSE values of approximately 0.36, 0.117, 0.03, and 0.009 for bit-widths ${\displaystyle b=1,2,3,4}$, respectively.^[1]

TurboQuant_prod

TurboQuant_prod is optimized for unbiased inner-product estimation. The authors note that an MSE-optimized quantizer may introduce bias when used to estimate inner products. To address this, TurboQuant_prod first applies TurboQuant_mse with bit-width ${\displaystyle b-1}$, then applies a one-bit Quantized Johnson–Lindenstrauss transform to the remaining residual vector.^[1]

Let $${\displaystyle r=x-Q_{\mathrm {mse} }^{-1}(Q_{\mathrm {mse} }(x))}$$ be the residual after MSE quantization, and let ${\displaystyle \gamma =\|r\|_{2}}$. The QJL step stores a sign vector for the residual. For ${\displaystyle \gamma \neq 0}$, this can be written using the normalized residual ${\displaystyle u=r/\gamma }$: $${\displaystyle qjl=\operatorname {sign} (Su),}$$ where ${\displaystyle S\in \mathbb {R} ^{d\times d}}$ is a random projection matrix. Since the sign function is invariant under positive rescaling, this is equivalent to ${\displaystyle \operatorname {sign} (Sr)}$ when ${\displaystyle r\neq 0}$. If ${\displaystyle \gamma =0}$, the residual correction is zero.

TurboQuant_prod stores the MSE quantization, the QJL sign vector, and the residual norm: $${\displaystyle Q_{\mathrm {prod} }(x)=\left[Q_{\mathrm {mse} }(x),qjl,\gamma \right].}$$

The dequantized vector is reconstructed as $${\displaystyle {\tilde {x}}={\tilde {x}}_{\mathrm {mse} }+{\frac {\sqrt {\pi /2}}{d}}\,\gamma S^{\top }qjl.}$$

The paper proves that TurboQuant_prod is unbiased for inner-product estimation: $${\displaystyle \mathbb {E} _{\tilde {x}}\left[\langle y,{\tilde {x}}\rangle \right]=\langle y,x\rangle .}$$ It also gives the distortion bound $${\displaystyle D_{\mathrm {prod} }\leq {\frac {\sqrt {3\pi }}{2}}\cdot {\frac {\|y\|_{2}^{2}}{d}}\cdot {\frac {1}{4^{b}}}.}$$