RaBitQ and the error bound

One bit, with a guarantee

RaBitQ (Gao and Long at NTU Singapore, arXiv 2405.12497) rotates the vector, just like TurboQuant, then keeps only the sign of each coordinate, that is, whether it is positive or negative: a single bit. One bit per dimension sounds far too crude to search with, and on its own it is. The breakthrough is what the rotation buys: it lets you prove a bound (a guaranteed ceiling on how wrong the similarity estimate can ever be), and that bound tightens as the number of dimensions grows.

This is why a single bit works for real embeddings, which have hundreds of dimensions. Drag the dimension count below. In low dimensions the 1-bit estimate scatters all over; as dimensions grow, it concentrates tightly around the true value (a high-dimensional effect called concentration: random quantities cluster close to their average once there are enough of them). The error shrinks roughly like one over the square root of the dimension.

Why a proof matters here

For more than a decade, product quantization was the default with no theory behind it: you tuned the number of chunks until recall looked acceptable. RaBitQ changed the conversation by hitting, in the limit, the best error any quantizer could achieve for high-dimensional vectors, a limit from a 2017 result by Alon and Klartag. Extended RaBitQ (2025) generalizes the method from one bit to several bits per dimension, trading more memory for more accuracy along the same principled curve. It already ships inside production databases such as Milvus and Elasticsearch.

Key takeaways