Module rotate 

The random rotation every vector goes through before it is quantised (10 section 3).

RaBitQ quantises a coordinate to its sign, and a sign carries information only when the coordinates are all about the same size. Real embeddings are not like that: a handful of dimensions hold most of the energy, and the sign of the rest is close to a coin toss. A random rotation fixes it, because rotating a vector by a random orthogonal matrix spreads its length evenly over the coordinates while leaving every distance and every angle exactly where it was. That is the whole reason the estimator’s error bound holds.

use yo_vector::Rotation;

let r = Rotation::new(8, 42);
let mut v = [1.0f32, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0];
r.apply(&mut v);

// The length did not move, and neither did anything else about the vector.
let len: f32 = v.iter().map(|x| x * x).sum::<f32>().sqrt();
assert!((len - 1.0).abs() < 1e-5);
// The one coordinate that held everything now holds a share of it.
assert!(v.iter().all(|x| x.abs() < 0.95));

Why this shape and not a matrix

The obvious rotation is a dense D by D orthogonal matrix from a QR decomposition, and it costs D^2 multiplies per vector. At 768 dimensions that is 590 thousand multiplies to insert one vector, and the ingest target is fifty thousand vectors a second on one core, which asks for 29 GFLOP/s of nothing but rotation. It does not fit, so the rotation has to be structured.

The usual structured answer is a random sign flip followed by a Hadamard transform, which is D log D and lovely, and needs D to be a power of two. Padding 768 up to 1024 would make a one bit code 128 bytes instead of 96, which is a third more index for every vector in the collection, so that is not free either.

What is here is the same idea without the power of two. A round flips the sign of a random half of the coordinates, pairs them all up at random, and replaces each pair with its sum and its difference over the square root of two. Every step of that is orthogonal by construction rather than approximately orthogonal after rounding, and a quarter turn on a pair splits whatever it was holding evenly between the two, which is the part that actually spreads a spike out. Pairing at random rather than by a fixed stride is what lets any coordinate reach any other, so log2(D) rounds and a couple more is enough.

The angle is not random, and that is deliberate. A round with a random angle keeps roughly nine tenths of what the larger side was holding, so a spike only decays like 0.9^rounds and it takes something like sixty rounds at 256 dimensions to flatten. A quarter turn halves it every time and takes eight. The randomness the estimator needs comes from the pairing and the signs, and there is plenty of it.

It is not written down anywhere

A rotation is dim and a seed, and both live in the collection’s catalogue entry. Rebuilding it is deterministic on every machine and every target, because the generator underneath is, so the file never holds the tables and two processes that open the same collection compute the same rotation.

Structs

Rotation

A random orthogonal transform, rebuilt from its seed rather than stored.