Missing ANN regime: 2–4-bit scalar-quantized FastScan search index

[shaal]

Missing ANN regime: 2–4-bit scalar-quantized FastScan search index

Summary

ruvector has strong ANN coverage but is missing the 2–4-bit scalar-quantized search regime that every mainstream production vector DB lives in (FAISS IndexPQFastScan, Qdrant, Milvus IVF-SQ). This issue makes the case for adding it as a small, self-contained crate (ruvector-turbovec, proposed in ADR-194). A working scalar-reference milestone (M1) is implemented and validated — see the companion PR #521.

The gap

Crate	Index family	Quantization	Suitable for "search 10M vectors for nearest 10"?
ruvector-core	HNSW (graph)	none (f32)	yes, but full f32 memory
ruvector-diskann	DiskANN (graph)	none / PQ-ish	yes
ruvector-rairs	IVF (ADR-193)	optional	yes
ruvector-rabitq	Flat + rotation	1-bit only	yes, but 1-bit caps recall
ruvllm turbo_quant.rs	— (value codec)	2.5–4 bit	no — KV-cache compressor, not an index

Two things sit near this regime but neither closes it:

1. ruvector-rabitq is 1-bit. It's excellent when memory dominates, but on 1536–3072-dim production embeddings (OpenAI text-embedding-3, Cohere, Voyage) you need an exact-rerank pass over the raw f32 originals to hit production R@1 — which re-inflates memory back toward the f32 footprint, partly defeating the point.
2. ruvllm/src/quantize/turbo_quant.rs is a TurboQuant value codec for transformer KV-cache / embedding compression. It has no inverted lists, no top-k heap, no FastScan LUT kernel, no filtered/allowlist search, no stable IDs/deletion. Wrong abstraction for search.

What's missing, concretely

• 2–4 bits per dimension (not 1, not 32).
• Codebook-free scalar quantization — no k-means training, online ingest.
• A FastScan-style nibble-LUT SIMD kernel that scores 16/32 candidates per vector instruction without ever materializing f32.
• Competitive recall without a mandatory f32 rerank pass.

Why it matters

• Memory/recall trade-off that's actually new. The per-vector length-renormalization scalar (c_x) makes the inner-product estimator unbiased, so 2/4-bit recall holds without the rerank tax that 1-bit RaBitQ pays. The memory win is real, not borrowed-back at query time.
• Parity with the field. It puts ruvector in the same regime as FAISS IndexPQFastScan / Milvus IVF-SQ, which is what most teams reach for when they outgrow flat f32 but can't afford 1-bit's recall hit.
• Reuse, not sprawl. It implements the existing ruvector_rabitq::AnnIndex trait and reuses RandomRotation — so it drops into the same dispatcher/consumers with no new plumbing, and adds exactly one workspace crate.
• Roadmap fit. The same block-SoA codes can later back an IVF posting list (IVF-SQ-FastScan) — a natural composition with ruvector-rairs (ADR-193). It's also adjacent to the in-flight SymphonyQG research (research(nightly): SymphonyQG — graph-coupled 4-bit FastScan neighbor scoring #443, research(nightly): symphonyqg — co-designed 1-bit graph quantization (SIGMOD 2025) #428: graph-coupled 4-bit FastScan scoring), and complements the merged TurboQuant KV-cache work (feat(ruvllm): TurboQuant KV cache & vector compression #297) by covering the search-index side those didn't.

Evidence it works (M1, measured)

n=5,000 uniform-random vectors (worst case for ANN), dim=256, k=10, no f32 rerank, vs exact brute-force L2:

Width	recall@10	compression	mean cosine bias
1-bit	0.308	25.6×	+0.0005
2-bit	0.561	14.2×	+0.0001
4-bit	0.879	7.5×	−0.0000

Recall rises monotonically with bit-width; near-zero bias confirms the unbiased estimator. 16 unit + 1 doc-test pass; clippy clean. Reproduce with cargo run --release -p ruvector-turbovec.

Proposed path

Tracked by ADR-194. Incremental milestones:

1. M1 — scalar reference (this PR): rotation reuse + Lloyd–Max 2/4-bit SQ + TQ+ calibration + unbiased scoring + IdMapIndex (O(1) delete, filtered search). ✅ implemented & validated.
2. M2 — FastScan nibble-LUT SIMD kernel (AVX2 + NEON), fuzzed bit-identical to the scalar oracle.
3. M3 — .tv persistence.
4. M4 — AVX-512BW kernel + ruvector-rulake dispatcher registration.

The scalar M1 scorer is deliberately the determinism oracle the SIMD kernels must match bit-for-bit, so the perf work lands without risking correctness.

Ask

Adopt ADR-194 and land M1 (#521) as the foundation, then iterate on the SIMD milestones. Feedback welcome on the reuse boundary (rabitq trait/rotation), the ADR-193 IVF composition, and whether the Lloyd–Max math should be hoisted into a shared ruvector-math crate rather than living in the codec.

[shaal]

Roadmap checklist — divergences from the TurboQuant paper (arXiv:2504.19874)

Reviewing M1 against the paper (not just the RyanCodrai/turbovec reference impl, which simplifies it) surfaced five tracked gaps. Full detail is in ADR-194 → "Divergences from the TurboQuant paper". M1 is internally consistent — these are scope boundaries / follow-ups, not bugs.

• D1 — paper-grade unbiased estimator (M5). M1 scores with a heuristic per-vector scalar c_x = ⟨r,r̂⟩/⟨r̂,r̂⟩ (empirically near-unbiased, no guarantee). The paper's unbiasedness is a two-stage MSE quantizer + 1-bit QJL on the residual. Add the QJL-residual stage (flag-gated) as a recall/accuracy upgrade if c_x underperforms on clustered data.
• D2 — d-aware Beta-optimal codebooks (M6). M1 quantizes against the N(0,1) limit + empirical TQ+ calibration. The paper uses Max-Lloyd tables for the exact Beta marginal per (bit-width, dimension). Generate those offline; keep N(0,1)+calibration as the fast default.
• D3 — 3-bit width. ✅ Done in PR feat(turbovec): multi-bit TurboQuant FastScan ANN index (ADR-194 M1) #521 (commit 4ceec40): added BitWidth::Three (8-level Max-1960 N(0,1) levels). Measured recall 0.767 at 9.8× (112 B/vec), landing between 2-bit (0.561) and 4-bit (0.879).
• D4 — distortion-bound test oracle. ✅ Done in PR feat(turbovec): multi-bit TurboQuant FastScan ANN index (ADR-194 M1) #521 (commit c39d57e): quantizer_mse_within_paper_bound asserts per-coordinate MSE under D_mse ≤ (√3·π/2)·4^(−b) and within 5% of the Max-1960 optimum, all widths. (Full-pipeline D_prod still to come.)
• D5 — estimator variance. Paper bounds it (ranking confidence / early-termination). Deferred until IVF/rerank composition (ADR-193) needs it.

Already matches the paper (no action): f32 norm storage for Euclidean recovery; data-oblivious / zero-training online ingest; full-precision (rotated, un-quantized) query vs quantized DB. FastScan SIMD (M2–M4) is a FAISS-lineage engineering layer, not part of the paper.

[shaal]

M5 design note — paper-grade unbiased scoring via a QJL residual stage (ADR-194 §D1)

Status: draft / not started. Companion to ADR-194 milestone M5. Target: a follow-up PR after M1 (#521) lands.

Goal

M1 makes scoring empirically near-unbiased with a single per-vector scalar c_x = ⟨r,r̂⟩/⟨r̂,r̂⟩ (a least-squares magnitude correction, 0 extra bits). The TurboQuant paper (arXiv:2504.19874) instead achieves provable unbiasedness with a two-stage estimator: the scalar-quantized reconstruction plus a 1-bit QJL sketch of the residual. M5 adds that second stage as an opt-in scoring mode, so we keep c_x as the zero-overhead default and offer QJL when recall must approach the f32-rerank path at a fraction of the memory.

c_x corrects a scalar (vector magnitude). QJL corrects the full residual direction in a rank-m subspace — strictly more powerful, at a cost of m bits/vector.

The estimator

Let r = P·û be the rotated unit DB vector, r̂ its scalar-quantized reconstruction (current code), and the residual e = r − r̂. Draw a fixed seeded projection S ∈ ℝ^{m×d} (iid sign or Gaussian rows, shared across all vectors, like the rotation). Store per vector:

• the m sign bits b_j = sign(⟨S_j, e⟩) (m/8 bytes), and
• the residual norm ‖e‖ (one f32).

For a full-precision rotated query s (already computed once per query in search_core), the QJL estimate of the residual's contribution is unbiased:

⟨s, e⟩  ≈  ‖e‖ · √(π/2) · (1/m) · Σ_j  b_j · (S·s)_j

So the total inner-product estimate becomes:

⟨s, r⟩  ≈  ⟨s, r̂⟩            (current ip_unit term)
          + ‖e‖·√(π/2)·(1/m)·Σ_j b_j·(S·s)_j     (new QJL residual term)

In QJL mode the c_x multiply is dropped (the paper's estimator is ⟨y, x̂_mse + x̂_qjl⟩, no scalar). c_x and QJL are alternative unbiasing mechanisms, not stacked.

Where it slots into the code

index.rs — storage (SoA fields):

enum ScoringMode { Renorm, Qjl { bits: usize } }   // Renorm = today (default)
// new fields, populated only in Qjl mode:
qjl_proj: Option<QjlProjection>,  // seeded S, mirrors `rotation: RandomRotation`
qjl_bits: Vec<u8>,                // m/8 bytes per vector (flattened SoA)
res_norms: Vec<f32>,             // ‖e‖ per vector

encode_and_store — after the existing quantize+reconstruct loop (which already computes rhat per coord for c_x): accumulate the residual e_i = r_i − rhat_i, then in Qjl mode sketch it:

// reuse the rhat values already computed in the c_x loop
let e: Vec<f32> = r.iter().zip(&rhat).map(|(ri, rh)| ri - rh).collect();
self.res_norms.push(l2(&e));
self.qjl_bits.extend(self.qjl_proj.as_ref().unwrap().sign_sketch(&e)); // m bits
// Renorm mode: skip the above, keep pushing c_x into `corr` as today

Note the loop already materializes rhat; M5 just keeps the residual instead of discarding it. Minimal added work at encode time.

estimate_l2 — per query, hoist Ss = S·s once (in search_core, next to where s is built), then per candidate add the residual term:

// Renorm mode (today):
let cos_est = self.corr[pos] * ip_unit;
// Qjl mode:
let resid = self.res_norms[pos] * SQRT_PI_2 * inv_m * signed_sum(&self.qjl_bits[pos*mb..], ss);
let cos_est = ip_unit + resid;     // no c_x

signed_sum is Σ_j (±1)·Ss[j] = (Σ Ss[j] where b_j=+1) − (Σ where b_j=−1).

Cost

	Renorm (M1)	Qjl(m)
Extra bytes/vec	0 (c_x reuses corr)	m/8 + 4 (‖e‖)
Encode	as today	+ sketch m dots over the residual
Query setup	—	Ss = S·s, once: O(m·d) (or O(m log d) if S is a structured ±1 rotation)
Per-candidate scan	O(d)	+O(m) signed accumulation

Example d=256, m=64: +12 bytes/vec — still ~80× smaller than an f32 rerank (1024 B), while restoring most residual fidelity.

Determinism, memory accounting, API

• S is seeded (constructor arg, like the Hadamard seed) → bit-identical sketches across runs; the M1 scalar scorer stays the determinism oracle.
• memory_bytes() must add qjl_bits.len() + res_norms.len()*4 + qjl_proj.bytes().
• Public API: TurboVecIndex::with_scoring(dim, bw, seed, ScoringMode::Qjl { bits }); Renorm remains the default ctor so existing callers are unchanged.

Tests / acceptance

• Unbiasedness: mean signed IP error in Qjl mode ≤ Renorm mode, and → 0 as m grows (variance ~ 1/m). Extend the existing estimator_is_approximately_unbiased test with a Qjl arm.
• Recall lift: at 2-bit, Qjl(m) recall > plain 2-bit and approaches the 2-bit-+-f32-rerank ceiling at far lower memory; report the recall/byte curve in the demo.
• Determinism: same seed → identical bits (extend determinism_same_seed_same_codes).
• Distortion: the D4 oracle's D_prod half becomes checkable here (residual term restores the IP the MSE stage drops).

Risks / open questions

• m is a new knob. QJL variance ~ 1/m; too-small m injects noise that can underperform c_x. Mitigation: default Renorm; document a recommended m ≈ d/4 starting point; benchmark before promoting.
• Structured vs dense S. Dense Gaussian S is O(m·d) query setup and m·d floats stored (or regenerated from seed). A second randomized-Hadamard-style ±1 projection gives O(m log d) setup and no stored matrix — preferred; reuse ruvector_rabitq::RandomRotation machinery if m ≤ d.
• FastScan interaction (M2). The per-candidate residual term is a sign-controlled sum of m query values — not a popcount, so it needs its own SIMD path (gather/sign-flip/add) alongside the nibble-LUT. Keep it behind the same VectorKernel determinism contract. Decide whether QJL ships before or after the SIMD kernel; the scalar M5 is the oracle either way.
• Memory honesty. Always report Qjl's m/8 + 4 overhead in memory_bytes() and the demo — never quote the code-only compression ratio in Qjl mode.

References

• TurboQuant — arXiv:2504.19874 (two-stage MSE + QJL-residual estimator)
• QJL — arXiv:2406.03482 (the 1-bit JL sketch + unbiased IP estimator)
• M1 baseline: crates/ruvector-turbovec/src/index.rs (encode_and_store, estimate_l2), ADR-194 §T4 / §D1.