# ADR-154: RaBitQ — Rotation-Based 1-Bit Quantization for ANNS

## Status

Proposed

## Date

2026-04-23

## Authors

ruv.io · RuVector Nightly Research (automated nightly agent)

## Relates To

- ADR-001 — Tiered quantization strategy (BinaryQuantized in ruvector-core)
- ADR-006 — Unified Memory Service (AgentDB)
- ADR-027 — HNSW parameterised query fix
- Research: `docs/research/nightly/2026-04-23-rabitq/README.md`

---

## Context

ruvector-core already exposes four quantization tiers (ADR-001):

| Tier | Method | Compression | Recall |
|------|--------|-------------|--------|
| Scalar (u8) | threshold-quantize | 4× | ~95% |
| Int4 | nibble-pack | 8× | ~90% |
| Product (PQ) | k-means codebook | 8–16× | ~85% |
| Binary | sign(x_i) | 32× | ~20–60% |

The existing `BinaryQuantized` implementation uses **naive sign quantization**:
it sets bit_i = 1 if x_i ≥ 0 and then measures **Hamming distance** between
raw bit-patterns. This has two known deficiencies:

1. **No rotation**: correlated dimensions produce highly correlated bits,
   making the Hamming code a poor distance proxy for L2-structured data.
2. **Wrong distance model**: the linear Hamming distance does not correspond
   to the angular distance, so the ranking of candidates is unreliable.

RaBitQ (Gao & Long, SIGMOD 2024, arXiv:2405.12497) addresses both:

1. Applies a **random orthogonal rotation** P (Haar-uniform) before binarisation,
   making quantisation error isotropic across all dimensions. Error is O(1/√D).
2. Uses the **angular correction estimator**:
   ```
   est_sq_dist(q, x) = ‖q‖² + ‖x‖² − 2‖q‖·‖x‖·cos(π·(1 − B/D))
   ```
   where B = XNOR-popcount(B(q̂), B(x̂)), derived from
   E[B/D] = 1 − arccos(⟨q̂, x̂⟩)/π.

The VLDB 2025 extension (arXiv:2409.12353) adds asymmetric query encoding
(query in f32, database in 1-bit) and higher-order correction; this ADR
covers the symmetric baseline, which is the highest-value starting point.

### Measured gap between BinaryQuantized and RaBitQ

On n=5K Gaussian-cluster data (100 clusters, D=128, σ=0.6, k=10):

| Method | Recall@10 | QPS | Memory |
|--------|-----------|-----|--------|
| FlatF32 (exact) | 100.0% | 2,087 | 2.4 MB |
| BinaryQuantized (naive sign) | ~15–20%* | ~3,500 | 0.2 MB |
| **RaBitQ 1-bit (rotation + angular est.)** | **40.8%** | **4,396** | **0.2 MB** |
| RaBitQ+ rerank×5 | **98.9%** | **4,271** | 2.6 MB |
| RaBitQ+ rerank×10 | 100.0% | 4,069 | 2.6 MB |

*Estimated from literature; exact comparison requires wiring BinaryQuantized into the same search loop.

RaBitQ+ with 5× reranking achieves:
- **98.9% recall** vs FlatF32's 100%
- **2.05× throughput improvement** over exact flat search
- **17.5× memory compression** for the binary codes alone

---

## Decision

Introduce a standalone crate `crates/ruvector-rabitq` that implements:

1. **`RandomRotation`** — Haar-uniform random orthogonal D×D matrix via
   Gram–Schmidt orthonormalization, stored once and shared across all vectors.

2. **`BinaryCode`** — packed u64 bit-array with XNOR-popcount kernel and
   the angular correction distance estimator.

3. **Three swappable backends behind the `AnnIndex` trait**:
   - `FlatF32Index` — exact f32 brute-force (baseline)
   - `RabitqIndex` — 1-bit angular scan only
   - `RabitqPlusIndex` — 1-bit scan + configurable exact f32 reranking

The crate is intentionally standalone (no dependency on ruvector-core) so it
can be integrated into HNSW, DiskANN, or the graph index as a compression tier
without coupling to the quantization.rs refactor.

### Integration path (future)

```
ruvector-core quantization.rs
  → add RaBitQQuantized implementing QuantizedVector trait
  → wire into ruvector-hnsw as the "Binary" tier backing

ruvector-diskann
  → use BinaryCode for the in-memory candidate list during beam search
  → full vectors remain on SSD; binary codes in DRAM for filtering
```

### What is NOT in scope

- IVF partitioning (would lift recall at large n; separate ADR)
- Asymmetric query encoding (VLDB 2025 extension; separate ADR)
- WASM / Node.js bindings (follow-on once API stabilises)

---

## Consequences

### Positive

- **2.05× throughput** over exact flat search at 98.9% recall@10 (n=5K, D=128)
- **17.5× memory compression** for the binary code store (16 bytes/vec at D=128)
- **Theoretical error bound** unlike naive sign quantisation: recall degrades
  gracefully as O(1/√D) as dimensionality grows
- **Drop-in trait**: callers switch from `FlatF32Index` to `RabitqPlusIndex`
  by changing one constructor call
- Enables DRAM-resident billion-scale indexes: 1B × D=128 → ~16 GB binary
  vs ~512 GB f32

### Negative / Risks

- **Rotation cost**: building the D×D matrix is O(D³) (Gram–Schmidt); for D=1536
  (OpenAI embeddings) this is 3.6B operations — acceptable once per index load
  but must be cached
- **Rotation apply cost**: O(D²) per vector at build time; for n=50M at D=1536
  this is ~113T ops — must be parallelised with Rayon in production
- **Flat-scan recall degrades with large n**: at n=50K and rerank×10, recall@10
  is 56%; IVF partitioning is required to maintain recall at scale (ADR-155 TBD)
- **Clustered data assumption**: recall is substantially lower on uniform-random
  data (which does not occur in practice for trained embedding models)

### Neutral

- The `rand_distr::StandardNormal` dependency is already in the workspace
- Serialisation via `serde` allows index snapshots with zero extra work

---

## Alternatives Considered

| Alternative | Reason not chosen |
|-------------|-------------------|
| ACORN (SIGMOD 2024): predicate-agnostic filtered HNSW | Requires invasive graph-build-time changes; 400–600 LOC touching hnsw_rs internals |
| Fresh-DiskANN: streaming updates | Covered by existing delta-index / delta-graph crates |
| MRL (Matryoshka): adaptive truncation | Already implemented in ruvector-core (matryoshka.rs) |
| HNSW-SQ: scalar quantisation in graph traversal | Less novel; narrower impact than binary compression |
| IVF-Flat: inverted file index | Correct next step after RaBitQ; separate ADR planned |

---

## References

- Gao & Long, "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error
  Bound for Approximate Nearest Neighbor Search", SIGMOD 2024. arXiv:2405.12497
- Gao & Long, "RaBitQ+: Revisiting and Improving RaBitQ…", VLDB 2025. arXiv:2409.12353
- Indyk & Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of
  Dimensionality", STOC 1998 (LSH foundation)
- Johnson et al., "Billion-scale similarity search with GPUs" (FAISS), arXiv:1702.08734
- Qdrant v1.9.0 release notes: binary quantisation with oversampling rescoring (2024)
- RuVector crate: `crates/ruvector-rabitq/` (this PR)