Spending bits where distance errors come from: variance-optimal allocation for unbiased vector codes

Vector search systems compress each stored embedding into a short code and compare queries against these codes rather than against the full vectors. The best current codes, RaBitQ and its multi-bit extension, randomly rotate each vector and then round every coordinate to the same number of bits. The rounding is designed so that the estimated distance is correct on average. The random rotation has a cost: it spreads the vector's energy evenly across coordinates, which discards the fact that real embeddings concentrate most of their energy in a few directions. Classical compression theory says bits should go where the energy is. Classical theory, however, measures error by how well each vector is reconstructed, not by how accurately query-to-vector distances are estimated.

This note proposes an allocation rule chosen by the second criterion. The embedding is split into blocks of principal directions. Each block is compressed independently with an unbiased RaBitQ-style code. For each block the method chooses two numbers: how many random measurements to keep, and how many bits to spend on each measurement. The choice minimizes the predicted variance of the distance estimate under a fixed total bit budget. Every block stays unbiased, so the whole estimate stays unbiased. What changes is where the estimator's noise sits, and the claim is that it should sit where queries carry little energy.

Core Claim

Consider the asymmetric setting, where the query $q$ is kept at full precision and only the database vector $x$ is coded. Split both vectors into blocks $j = 1,\dots,J$ along principal directions, and code block $x_j$ by taking $M_j$ random projections, each quantized to $b_j$ bits with the Extended RaBitQ estimator. Each block's estimate of $\langle q_j, x_j\rangle$ is then unbiased. Its variance is approximately

$$ V_j(M_j,b_j) \approx \frac{\mathbb{E}\|q_j\|^2\,\mathbb{E}\|x_j\|^2}{M_j}\left(a_j + c\,4^{-b_j}\right). $$

In this formula, $a_j$ is the variance added by projecting to fewer dimensions than the block has, and it is zero when $M_j$ equals the block dimension $d_j$. The term $c\,4^{-b_j}$ is the rounding variance, and it shrinks by a factor of four per added bit. The $1/M_j$ scaling comes from averaging independent projections, the same averaging that gives RaBitQ its $O(1/\sqrt{D})$ error.

The allocation solves

$$ \min_{\{M_j,b_j\}} \sum_j V_j(M_j,b_j) \quad \text{subject to} \quad \sum_j M_j b_j \le B,\; b_j \in \{1,2,4,8\},\; M_j \le d_j, $$

where $B$ is the bit budget per vector.

This rule differs from classical reverse water-filling in two ways, both testable. First, each block's weight is the product of query energy and data energy, rather than data energy alone. When queries and data share a spectrum, the rule therefore concentrates bits roughly twice as steeply on the leading directions. Second, blocks can take a fractional rate below one bit per dimension without becoming biased. They do this by keeping fewer measurements ($M_j < d_j$) rather than being truncated to zero. The choice between many coarse measurements and few fine ones, whose optimum Li and Slawski left open, is resolved here per block by the ratio $a_j/c$. This mirrors the low-noise versus high-noise regimes of Regime Change: Bit-Depth Versus Measurement-Rate in Compressive Sensing.

Relation to Prior Work

The method builds on the unbiased hypercube and grid estimators of RaBitQ and Extended RaBitQ. Both apply one global rotation and the same bit depth to every coordinate. We keep their estimator but replace the uniform budget with a per-block one.

Pairwise Quantization supplies the idea of making the objective aware of the query distribution: it transforms data by the query second-moment matrix before standard product quantization. That paper also constrains our design. Its unweighted objective over all pairs lost to OPQ on top-1 recall. We therefore test a ranking-weighted variant in which the energy terms are estimated only over query–true-neighbor pairs.

On the measurement side, Simple strategies for recovering inner products from coarsely quantized random projections motivates the work. It shows that normalized estimators make 3–5 bits nearly lossless, and it leaves the choice of measurement count versus bits under a budget open. Low-Complexity Rate-Distortion Optimization of Sampling Rate and Bit-Depth for Compressed Sensing of Images solves the same choice jointly, but for image reconstruction quality measured by PSNR, not for distance estimation.

The rate-distortion allocators Radio and RDO-Q contribute the optimization machinery, dual ascent and linear-time channel allocation. Both minimize reconstruction or task error for network weights, and neither considers pairwise distances.

Research Program

The work has three parts.

The first is analysis. We will derive $a_j$ and $c$ for the Extended RaBitQ estimator applied after a random projection within a block, including the variance from the stored per-block norm. We will then show that the allocation separates into a per-block choice of bit depth, depending only on $a_j/c$, plus a global Lagrange multiplier that sets the measurement counts. The per-block bit depth minimizes $b(a_j + c\,4^{-b})$. This predicts 1-bit codes for blocks whose projection noise dominates and multi-bit codes for leading blocks kept at full rank.

The second is an encoder. It computes PCA blocks with sizes that are multiples of 64, calibrates the energy terms on training queries, solves the allocation by exhaustive search over the small bit-depth set with a bisection on the multiplier, and writes codes with per-block norms, counted inside $B$. Restricting bit depths to powers of two is deliberate. The file notes that 3- and 5-bit packing is costly on SIMD hardware, and that uneven widths across small blocks cause irregular execution on GPUs. Uniform bit depth within a block keeps each block's scan kernel identical to existing RaBitQ kernels.

The third is the ranking-weighted variant, which addresses the tension between global unbiasedness and top-$k$ accuracy noted in the file: estimate the energy terms only from query–true-neighbor pairs.

Baselines

The naive reference is uniform Extended RaBitQ at the same total bits, as in Extended RaBitQ. It is also the strongest existing method on this question. It reports more than 95% recall at 6.4x compression and more than 99% recall at 4.5x compression on OpenAI text embeddings without re-ranking on raw vectors. We will reproduce those operating points with the released design before comparing against them.

Beating it means one of two things at matched bits per vector, including norm overhead, and matched IVF probe settings. The first is higher recall@10 at 16x compression or more, where uniform codes are weakest. The second is equal recall at 20% fewer bits.

The second baseline is the same block structure allocated by classical reverse water-filling on data eigenvalues, the reconstruction-error rule used in the Radio and RDO-Q line. It gets the same blocks and bit-depth set and differs only in the objective. This is the ablation that isolates the proposal's main ingredient, the query-weighted variance objective.

The third baseline is PCA truncation followed by uniform Extended RaBitQ, with the kept dimension tuned per budget on a validation split. This is the strongest simple competitor.

A fourth baseline is OPQ as in Pairwise Quantization's comparisons. It anchors the gap between biased and unbiased codes: on SIFT1M, 4-byte PairQ matched 16-byte OPQ in that paper, and PairQ will be included too.

All methods get the same training split and the same tuning budget, a grid of 20 settings per method per budget.

Why not just…?

Why not just drop low-variance directions with PCA and code the rest uniformly? This is the real threat. On embeddings with fast-decaying spectra it may capture most of the gain. Truncation is the special case of our rule with $M_j = 0$. It is biased, because the dropped blocks' inner products are set to zero, and it has no intermediate rate between zero and one bit per dimension. The proposal's advantage should appear only in the middle of the spectrum. If the comparison on GIST1M and OpenAI embeddings shows no recall difference at any budget, the fractional-rate mechanism is unnecessary, and we will report that.

Why not just allocate bits by reconstruction error, as rate-distortion theory usually does? Pairwise Quantization showed that reconstruction-optimal product quantization systematically underestimates distances. The two rules also prescribe different allocation slopes. The water-filling ablation tests directly whether the difference matters for recall, and whether measured estimator variance follows our model rather than the reconstruction-error model.

Why not just keep uniform codes and re-rank with full vectors? Re-ranking requires storing raw vectors, which removes the memory savings, as the Extended RaBitQ paper argues. On irregular data such as MSong, standard product quantization misses over 40% of true neighbors according to RaBitQ, so candidate pools are already damaged before re-ranking. We still report a re-ranking-with-compressed-codes setting for all methods.

Why not use E8 or Leech lattices for their space-filling gain? Lattice Transform Coding and Leech Lattice VQ show real reconstruction gains, the latter reporting 6.83 WikiText-2 perplexity on Llama-2 7B. However, no unbiased distance estimator exists for these lattices, and 24-dimensional blocks do not align with SIMD lanes. The lattice gain is orthogonal to allocation and could later replace the per-block quantizer.

Proposed Experiments

The datasets are SIFT1M, GIST1M, DEEP1M, MSong, Word2Vec, OpenAI 3072-dimensional embeddings, and MSMARCO at 100M vectors. The metrics are recall@10 against bits per vector, from 32x down to 4x compression, and queries per second on a fixed CPU. We will also report measured bias and variance of the distance estimator for every method.

No reported recall numbers were found on Lacuna for GIST1M, DEEP1M, or Word2Vec, or for QPS on MSMARCO. These are established fresh under our runs.

Three checks decide the question. The first is the predicted-versus-measured variance curve per block: if the variance model is wrong, the allocation has no basis. The second is a negative control on isotropic Gaussian data. There every block has equal energy, so the rule must reduce to uniform Extended RaBitQ with no gain, and any apparent gain would indicate a measurement artifact. The third is the recall comparison against PCA truncation and against water-filling on anisotropic real embeddings. There the method should win, and it should win most where queries and data share a spectrum.