Rotate, Round, Debias

A random rotation makes every input direction look the same; whatever quantizer rounds the result can be made exactly unbiased for free, by dividing out its own alignment with the original vector, or, at one extra bit, by sketching away what it leaves behind.

6 min read

Nearest-neighbor search over a billion embedding vectors cannot afford full precision: at 768 dimensions and four bytes each, a billion vectors is three terabytes before a single query is answered. Compressing each vector to a few bits per coordinate creates two errors at once, in the reconstructed vector itself and in the distances search actually needs, and a compressor with no guarantee on either cannot be trusted at scale.

Rotate the vector randomly, then round each coordinate independently: that recipe underlies RaBitQ [GL, SIGMOD ’24], TurboQuant [ZDHM, ICLR ’26], and a later extension of RaBitQ’s estimator to any bit budget [GGXYLW, SIGMOD ’25]. What follows is the recipe itself, not any paper’s specific claims: why the rotation works, and two ways to make the rounding after it exactly unbiased, one built on the classical Lloyd–Max scalar quantizer [Lloyd, IEEE-IT ’82].

Rotate a vector randomly and every direction looks the same; round it however you like, and the result can always be made an exactly unbiased estimator of any inner product, either by dividing out its own alignment with the original vector or by sketching away what it leaves behind.

One Rotation Erases the Direction

Distances between vectors reduce to inner products between unit vectors from a shared centroid; call them \(\mathbf{o}\) (stored) and \(\mathbf{q}\) (query). A fixed codebook, say a hypercube’s vertices, is only as good as the input’s alignment with it: \(\mathbf{o} = (1/\sqrt{d}, \dots, 1/\sqrt{d})\) lands exactly on a vertex, zero error, while \(\mathbf{o} = (1, 0, \dots, 0)\) lands far from all of them. Real embeddings have no reason to avoid the bad directions.

The fix: sample an orthogonal matrix \(\mathbf{P}\) uniformly at random (Haar measure) and quantize \(\mathbf{P}^\top \mathbf{o}\) instead. Since \(\mathbf{P}\) is independent of \(\mathbf{o}\), \(\mathbf{P}^\top \mathbf{o}\) is uniform on the sphere no matter what \(\mathbf{o}\) was: the worst case over directions becomes the average case over the rotation, for every input at once.

A uniform point on the sphere is \(\mathbf{g}/\|\mathbf{g}\|\) for \(\mathbf{g} \sim \mathcal{N}(\mathbf{0}, \mathbf{I}_d)\), since a standard Gaussian’s density is rotationally symmetric. The norm concentrates around \(\sqrt{d}\) (\(\mathbb{E}\|\mathbf{g}\|^2 = d\), fluctuating by \(1/\sqrt{d}\)), so each rotated coordinate \(u_i \approx g_i/\sqrt{d}\) behaves like an independent draw from \(\mathcal{N}(0, 1/d)\): quantizing it is, to good approximation, quantizing a single Gaussian.

Debiasing Is Free

The simplest codebook is one bit per coordinate: \(\mathcal{C} = \{\pm 1/\sqrt{d}\}^d\). Write \(\mathbf{u} := \mathbf{P}^\top \mathbf{o}\); since \(\mathcal{C}\) is a product set, the nearest codeword matches each coordinate’s sign independently, \(\bar{\mathbf{z}} := \mathrm{sign}(\mathbf{u})/\sqrt{d}\), and the reconstruction is \(\bar{\mathbf{o}} := \mathbf{P}\bar{\mathbf{z}}\).

Using \(\bar{\mathbf{o}}\) directly would be biased, since nearest-vertex rounding shrinks toward the codebook rather than \(\mathbf{o}\)’s scale. Decompose \(\mathbf{q} = \langle \mathbf{o}, \mathbf{q}\rangle\, \mathbf{o} + \sqrt{1 - \langle \mathbf{o}, \mathbf{q}\rangle^2}\, \mathbf{e}_1\) for a unit vector \(\mathbf{e}_1 \perp \mathbf{o}\), and take the inner product with \(\bar{\mathbf{o}}\):

\[ \langle \bar{\mathbf{o}}, \mathbf{q}\rangle = \langle \mathbf{o}, \mathbf{q}\rangle \langle \bar{\mathbf{o}}, \mathbf{o}\rangle + \sqrt{1 - \langle \mathbf{o}, \mathbf{q}\rangle^2}\, \langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle. \]

Dividing through by \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle\) (nonzero except on a measure-zero event) isolates what we want:

\[ \frac{\langle \bar{\mathbf{o}}, \mathbf{q}\rangle}{\langle \bar{\mathbf{o}}, \mathbf{o}\rangle} = \langle \mathbf{o}, \mathbf{q}\rangle + \sqrt{1 - \langle \mathbf{o}, \mathbf{q}\rangle^2}\cdot \frac{\langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle}{\langle \bar{\mathbf{o}}, \mathbf{o}\rangle}. \]

Proof that the leftover term has expectation zero

Claim: \(\mathbb{E}\!\left[\dfrac{\langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle}{\langle \bar{\mathbf{o}}, \mathbf{o}\rangle}\right] = 0\), where the expectation is over the random rotation \(\mathbf{P}\).

Let \(\mathbf{Q}\mathbf{v} := \mathbf{v} - 2\langle \mathbf{v}, \mathbf{e}_1\rangle \mathbf{e}_1\), the reflection across the hyperplane orthogonal to \(\mathbf{e}_1\): it fixes every vector orthogonal to \(\mathbf{e}_1\), in particular \(\mathbf{o}\), and sends \(\mathbf{e}_1 \mapsto -\mathbf{e}_1\). Haar measure on the orthogonal group is invariant under left-multiplication by any fixed orthogonal matrix, so \(\mathbf{Q}\mathbf{P}\) has exactly the same distribution as \(\mathbf{P}\).

Recompute the reconstruction using \(\mathbf{Q}\mathbf{P}\) in place of \(\mathbf{P}\). Since \(\mathbf{Q}^\top \mathbf{o} = \mathbf{Q}\mathbf{o} = \mathbf{o}\), the sign pattern is unchanged, \(\mathrm{sign}\big((\mathbf{Q}\mathbf{P})^\top \mathbf{o}\big) = \mathrm{sign}(\mathbf{P}^\top \mathbf{o})\), so the reconstructed vector becomes \(\mathbf{Q}\mathbf{P} \cdot \mathrm{sign}(\mathbf{P}^\top\mathbf{o})/\sqrt{d} = \mathbf{Q}\bar{\mathbf{o}}\). Because \(\mathbf{Q}\mathbf{P} \stackrel{d}{=} \mathbf{P}\), this shows \(\mathbf{Q}\bar{\mathbf{o}} \stackrel{d}{=} \bar{\mathbf{o}}\): rotating the whole picture by \(\mathbf{Q}\) changes nothing about the distribution of the reconstruction.

Now use that \(\mathbf{Q}\) is self-adjoint, fixes \(\mathbf{o}\), and negates \(\mathbf{e}_1\): \(\langle \mathbf{Q}\bar{\mathbf{o}}, \mathbf{o}\rangle = \langle \bar{\mathbf{o}}, \mathbf{Q}\mathbf{o}\rangle = \langle \bar{\mathbf{o}}, \mathbf{o}\rangle\), while \(\langle \mathbf{Q}\bar{\mathbf{o}}, \mathbf{e}_1\rangle = \langle \bar{\mathbf{o}}, \mathbf{Q}\mathbf{e}_1\rangle = -\langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle\). Combined with \(\mathbf{Q}\bar{\mathbf{o}} \stackrel{d}{=} \bar{\mathbf{o}}\), the pair \((\langle \bar{\mathbf{o}}, \mathbf{o}\rangle, \langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle)\) has the same joint distribution as \((\langle \bar{\mathbf{o}}, \mathbf{o}\rangle, -\langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle)\): the second coordinate is symmetric about zero given the first. Dividing a distribution symmetric about zero by a fixed nonzero conditioning value stays symmetric about zero, so \(\mathbb{E}\big[\langle \bar{\mathbf{o}}, \mathbf{e}_1\rangle / \langle \bar{\mathbf{o}}, \mathbf{o}\rangle \mid \langle \bar{\mathbf{o}}, \mathbf{o}\rangle\big] = 0\), and averaging over \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle\) proves the claim.

So \(\langle \bar{\mathbf{o}}, \mathbf{q}\rangle / \langle \bar{\mathbf{o}}, \mathbf{o}\rangle\) is an exactly unbiased estimator of \(\langle \mathbf{o}, \mathbf{q}\rangle\), computed from the stored bits, the query, and one extra scalar \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle\). It also concentrates tightly, an exponential tail in \(d\): \(|\text{estimate} - \langle \mathbf{o}, \mathbf{q}\rangle| = O(1/\sqrt{d})\) with probability \(1 - 2e^{-\Omega(t^2 d)}\).

Nothing here depended on \(\bar{\mathbf{z}}\) being a sign pattern. Swap \(\mathrm{sign}(\cdot)\) for any other fixed function of \(\mathbf{u}\), and \((\mathbf{Q}\mathbf{P})^\top \mathbf{o} = \mathbf{P}^\top \mathbf{o}\) still holds, so the same argument gives an unbiased estimator for any rounding rule, just by dividing by its realized alignment \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle\). So why not always just divide? Because unbiasedness alone says nothing about how large the error is, and a codeword chosen to minimize reconstruction error ought to do better.

The realized \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle\) concentrates too, around a constant worth computing since it reappears below. Using \(u_i \approx g_i/\sqrt{d}\), \(\langle \bar{\mathbf{o}}, \mathbf{o}\rangle = \frac{1}{\sqrt{d}}\|\mathbf{u}\|_1 \approx \frac{1}{d}\sum_i |g_i|\), which concentrates around \(\mathbb{E}|g_i|\):

\[ \mathbb{E}|g_i| = 2\int_0^\infty x \cdot \frac{1}{\sqrt{2\pi}} e^{-x^2/2}\, dx = \frac{2}{\sqrt{2\pi}}\Big[-e^{-x^2/2}\Big]_0^\infty = \sqrt{\frac{2}{\pi}} \approx 0.7979, \]

so the raw codeword lands, on average, at about 80% of \(\mathbf{o}\)’s own length in \(\mathbf{o}\)’s direction: \(\{\pm 1/\sqrt{d}\}^d\) was never built to minimize reconstruction error, only to match signs.

Spending the Bit Budget Well

What is the best \(2^b\)-point codebook for a coordinate distributed as \(\mathcal{N}(0, 1/d)\)? That is the classical scalar quantization problem Lloyd’s algorithm solves: partition the line into \(2^b\) intervals, represent each by its conditional mean, and iterate to a fixed point.

At \(b = 1\), by symmetry the optimal split is at zero and the optimal level is the conditional mean \(c = \mathbb{E}[g_i \mid g_i > 0] = \sqrt{2/\pi}\), the same half-normal integral as above: the MSE-optimal codeword \(\pm\sqrt{2/(\pi d)}\) is the same sign pattern, shrunk by \(\sqrt{2/\pi} \approx 0.7979\). Used directly, that shrinkage biases inner products by the same factor squared, \(\langle \tilde{\mathbf{o}}, \mathbf{o}\rangle \approx 2/\pi \approx 0.6366\), writing \(\tilde{\mathbf{o}}\) for the rescaled reconstruction. Dividing by that alignment, as before, would fix it, but there is a second way worth seeing.

Spend \(b - 1\) bits on \(\tilde{\mathbf{o}}\), form the residual \(\mathbf{r} := \mathbf{o} - \tilde{\mathbf{o}}\), and spend the last bit sketching \(\mathbf{r}\) with an independent random sign projection: a fresh Gaussian matrix \(\mathbf{S}\), one sign bit per coordinate of \(\mathbf{S}\mathbf{r}\), rescaled to be unbiased for \(\mathbf{r}\) itself, the same mechanics that make SimHash unbiased for inner products. Adding the coarse reconstruction and the debiased residual, \(\tilde{\mathbf{o}} + (\text{sketch of } \mathbf{r})\), is unbiased for \(\langle \mathbf{o}, \mathbf{q}\rangle\) at any \(b\), through a mechanism entirely different from division: sketching the leftover away instead of dividing it away.

Left, one bit: the raw codeword (dashed) sits past the MSE-optimal codeword (solid) by \(\sqrt{2/\pi}\). Right, two bits: four Lloyd–Max levels on the same density, the same construction at a larger budget.

The headline guarantee is a distortion bound, not a tail bound: expected squared error within \(\sqrt{3}\pi/2 \approx 2.72\times\) (1.45x at \(b=1\)) of the best any \(b\)-bit code could do on the hardest input, a limit from Shannon’s rate-distortion theory proved by a minimax argument, holding at every \(b\) from one construction.

Two Mechanisms, One Rotation

Rotating into noise and rounding coordinatewise says nothing about bias by itself. Fixing it is a separate question with two answers: dividing by the reconstruction’s own alignment, free and rule-agnostic; or sketching away the residual, at one extra bit, in exchange for a distortion bound. Both are exactly unbiased; which gives the smaller error at a given budget is the harder question.

The same recipe generalizes past search: it compresses a transformer’s key-value cache [ZDH, AAAI ’25] and gradients in federated learning [VBPMBM, ICML ’22], different vectors under the same requirement: whatever inner product gets computed downstream comes out unbiased.