Hypercube

4 min read

What is a Hypercube?

A hypercube is simply the generalization of a standard 3D cube into any arbitrary number of dimensions ($D$). It is easiest to understand by starting from zero and building upwards:

• 1D (Line Segment): Imagine a line segment stretching from $-1$ to $+1$. The two endpoints represent the "vertices."
• 2D (Square): If you add a second dimension, you get a square. Its four corners (vertices) sit at the coordinates: [+1, +1], [-1, +1], [-1, -1], and [+1, -1].
• 3D (Cube): Add a third dimension, and you get a standard cube. Its eight corners sit at coordinates where each position is either $+1$ or $-1$ (e.g., [+1, -1, +1], [-1, -1, -1]).
• $D$-Dimensional Hypercube: When you scale this up to high-dimensional vector spaces (such as $D = 128$ dimensions), the hypercube is a shape with $2^D$ corners (vertices). Every single one of these vertices is represented by a sequence of coordinates that are strictly bi-valued.

To keep these vertices sitting perfectly on a unit sphere (where the length of the vector is exactly $1$), we scale the coordinates so that each coordinate is either $+1/\sqrt{D}$ or $-1/\sqrt{D}$. For example, in a 4-dimensional hypercube, one of the vertices would be:

Why Was the Hypercube Chosen for RaBitQ?

The authors of RaBitQ selected the vertices of a normalized hypercube to act as their "codebook" for five key mathematical and engineering reasons:

1. It Maps Perfectly to 1-Bit Binary Strings (Maximum Compression)

Because every coordinate of a hypercube vertex is strictly bi-valued ($+1/\sqrt{D}$ or $-1/\sqrt{D}$), you do not need to store floating-point numbers.

You can encode each coordinate using just one single binary bit (where a positive sign $+1/\sqrt{D}$ is stored as a 1, and a negative sign $-1/\sqrt{D}$ is stored as a 0). This compresses a $D$-dimensional vector into a tight $D$-bit string.

2. It Spreads Perfectly Evenly (Symmetry)

To prevent compression bias, the representative vectors in a codebook should be distributed as uniformly as possible across the unit sphere. Because a hypercube is perfectly symmetric, its vertices spread perfectly and evenly across the unit hypersphere.

3. It Requires Zero Storage Space for the Codebook

In traditional Product Quantization (PQ), the database must physically store and materialize thousands of learned K-Means centroids in memory to act as the codebook.

With RaBitQ, because the hypercube is a deterministic mathematical shape, the codebook is purely conceptual. The engine never has to materialize or store the individual vertices; it only needs to physically save the random orthogonal rotation matrix $P$ used to rotate the hypercube.

4. It Enables Blazing-Fast CPU Bitwise Math

Because the hypercube vertices are represented as simple bit strings, comparing a database vector to a query vector does not require looking up slow tables in RAM.

Instead, the CPU can evaluate the query directly inside its registers using hardware-accelerated bitwise AND and popcount (bit-counting) instructions. This allows RaBitQ to run 3x faster than standard PQ on single-vector comparisons.

5. It Provides Predictable, Sharp Error Bounds

Because the hypercube has a rigid, known geometric structure, combining it with a random rotation matrix $P$ (a Johnson-Lindenstrauss Transformation) makes the error introduced by compression mathematically predictable.

The projection of these rotated hypercube vertices behaves as a highly concentrated, symmetric random variable with an expected error of exactly zero. This rigorous geometry allows RaBitQ to provide an unbiased estimator with a sharp, mathematically optimal error bound of $O(1/\sqrt{D})$.

Related reads

• RaBitQ — the quantization algorithm this geometry was chosen for
• Product Quantization (PQ) — the data-dependent alternative