TieredQ - Beating RaBitQ with Variance-Aware Bit Allocation

November 5, 2026

While building my own ANN index for digger.so, I was evaluating existing vector quantization algorithms to reduce RAM usage and storage costs. After playing around with TurboQuant and RaBitQ on some text embeddings I had the following idea for a new vector quantization approach:

Why compress all dimensions of a vector uniformly (lowering all dimensions to the same number of bits)? My intuition was that using a custom amount of bits per dimension based on its importance (variance) could improve retrieval performance (with respect to compressed vector data size).

After some experiments my vector quantization technique TieredQ was born and it is beating both TurboQuant and RaBitQ on all my benchmarks (recall compression ratio wise - but not always throughput QPS and index build time).

TieredQ github repo

How it works

TieredQ core algorithm:

PCA
Variance-aware greedy bit allocation per dimension (principal component)
Scalar quantization per dimension with allocated bit budget

TieredQ first subtracts a learned centroid from each vector, rotates the residual with PCA, and then hands out bits greedily to each dimension (0-8 per dim based on variance), wherever each extra bit reduces the expected error most.

Experiments (Benchmarks)

setup: compute recall baseline (full linear scan), compute recall on compressed vectors (full linear scan)

relevant metrics: compression time, query latency, retrieval performance (recall etc.) per compression data (recall per compressed vector data)

Based on: https://github.com/VectorDB-NTU/rabitq-turboquant-comparison/

Limits

Training and drift: PCA requires representative training data; its allocation can become less suitable as the distribution changes.
Execution cost: initial compression is more costly; variable bit widths complicate packing and fast distance kernels.
Objective mismatch: minimizing reconstruction MSE does not always maximize nearest-neighbor recall.
Dataset dependence: a flat PCA spectrum offers less opportunity for variance-aware allocation.

Previous Work: Transform Coding for ANN

After building TieredQ, I looked into whether variance-aware bit allocation had been explored before. As it turns out, the underlying idea has a surprisingly long history.

Transform Coding

TieredQ belongs to a family of compression techniques called transform coding, which has been around for decades. The basic idea is straightforward: transform the data into a representation where information is concentrated in fewer dimensions, then allocate more bits to the dimensions that matter most.

This is closely related to techniques used in JPEG, audio compression, and other signal-processing applications. PCA (also known as the Karhunen–Loève Transform in this context) is a natural choice because it decorrelates dimensions and orders them by variance.

For approximately Gaussian data, allocating bits according to the variance of each transformed dimension is well motivated by classical rate–distortion theory.

Transform Coding for Nearest Neighbor Search

Interestingly, this approach was already explored specifically for approximate nearest neighbor search.

Brandt (2010) — Transform Coding for Fast Approximate Nearest Neighbor Search in High Dimensions

Brandt proposed using PCA together with non-uniform bit allocation and scalar quantization to produce compact vector representations for nearest neighbor search.

This is conceptually very close to TieredQ: rather than spending the same number of bits on every dimension, the algorithm allocates more bits to components carrying more information.

Park et al. (2014) — Optimized Transform Coding for Approximate KNN Search

This follow-up work improved transform coding by identifying a weakness in variance-based bit allocation: dimensions with similar variance don't necessarily have the same quantization error.

Instead of relying solely on a theoretical variance model, Optimized Transform Coding (OTC) uses actual quantization distortion to make better allocation decisions.

This is particularly relevant to TieredQ, since it also allocates bits greedily based on the expected reduction in reconstruction error. The underlying optimization idea is therefore not new either.

How TieredQ Differs

TieredQ builds on these ideas but applies them to modern embeddings, with an emphasis on practical retrieval quality at a given compression ratio.

Its implementation combines:

Centroid-centered PCA: Learn a centroid from the dataset, subtract it, and rotate the residual vectors into PCA space to expose the variance structure.
Greedy bit allocation: Assign between 0 and 8 bits per principal component, prioritizing whichever additional bit produces the largest expected reduction in quantization error.
Per-dimension scalar quantization: Quantize each component independently using its assigned precision, rather than using a fixed number of bits across all dimensions.
Retrieval-focused evaluation: Compare recall at equivalent compressed vector sizes against modern approaches such as RaBitQ and TurboQuant, rather than looking only at reconstruction MSE.

The biggest difference from RaBitQ and TurboQuant is that TieredQ explicitly learns where the dataset's information is concentrated and distributes its bit budget accordingly.

RaBitQ relies on randomized rotation and binary quantization, while TurboQuant uses randomized rotation and scalar quantization together with techniques for controlling inner-product estimation error. Both emphasize theoretical guarantees and efficient, broadly applicable quantization.

TieredQ instead makes a different tradeoff: spend more effort learning the structure of the dataset to make better use of every stored bit.

Compared with earlier transform coding methods, TieredQ is less a fundamentally new algorithm and more a modern implementation of an established idea, evaluated against a new generation of ANN quantizers and embedding distributions.

Why Is This Interesting?

Historically, transform coding competed with Product Quantization (PQ), which often performed better at very low bit rates because it quantizes groups of dimensions jointly.

But modern embeddings can have highly non-uniform variance distributions. That creates an opportunity for techniques that allocate their precision unevenly instead of treating all dimensions equally.

And that's exactly what I'm seeing in my experiments.

On my benchmarks, TieredQ achieves better retrieval recall at comparable compressed vector sizes than both RaBitQ and TurboQuant.

That doesn't mean TieredQ is universally better. PCA requires dataset-specific training, the learned transform introduces additional costs, and my results currently measure compression efficiency rather than end-to-end query throughput.

But they suggest that a relatively simple, data-aware transform coder can still be highly competitive with modern ANN compression techniques.

References

#AI #coding #math