mirror of
https://github.com/ruvnet/RuVector.git
synced 2026-07-09 17:28:42 +00:00
18dedfac7b
* docs(bet4): pre-register LB-B&B IVF vs plain-IVF nprobe gate (FROZEN)
Closes the BET 4 caveat left open by ADR-201: the region-pruning IVF
kernel was only run against ACORN (BET 2), never against its natural
incumbent, plain IVF nprobe, on unfiltered ANN. Frozen gate: WIN = >=2x
member-scan reduction at matched recall@10 (R=0.95) AND wall-clock win
across nclusters in {64,256,1024}; KILL = <1.5x or wall-clock reverses.
Two controls: exact-vs-exact pruning-fraction probe + low-d (PCA-8)
soundness control. Honest prior: NO-GO lean (128-d concentration makes
the triangle-inequality bound loose) — the IVF-level companion to
ADR-199. Branch off clean main; B&B kernel rebuilt self-contained
(BET 2's lives only on #536).
* feat(bet4): M0 — self-contained BnBIvf kernel + oracle gate (exactness certified)
New crate ruvector-bet4-ivf-bench (deps: ruvector-rairs, rand).
- data.rs: aligned arxiv 128-d feature CSV loader.
- kernel.rs: BnBIvf — IVF probed in ascending lower-bound order with B&B
early termination (break when LB >= kth-best); LB(q,c)=max(0,|q-mu_c|-r_c),
r_c=max member radius. Full budget = exact; max_probe cap = nprobe analogue.
Built on ruvector-rairs kmeans so it shares centroids with the IvfFlat
incumbent (shared-index pre-reg requirement).
- oracle.rs: brute-force exact kNN + recall@k + shared true-L2 helper.
- M0 gate test PASSES on real arxiv slice: full-budget B&B == oracle
(recall@10 >= 0.999) → B&B invariant certified. clippy clean.
Frozen gate: docs/plans/bet4-ivf-pruning/PRE-REGISTRATION.md. Off clean main.
* feat(bet4): M1 — instrumented plain-IVF incumbent on shared index + faithfulness gate
BnBIvf::search_nprobe: the plain-IVF incumbent strategy (nprobe nearest
centroids, scan all members, no B&B) on the SAME centroids/lists as the
B&B contender, with member-eval counting. Refactored top-k accumulation
into shared consider()/finalize() so both strategies accumulate
identically and only the probe loop differs (shared-index pre-reg
requirement). New gate instrumented_nprobe_matches_rairs PASSES: recall
matches ruvector-rairs::IvfFlat within 0.01 at matched params → the
cost-measured incumbent is algorithmically the real one. 3 tests green.
* feat(bet4): M2/M3 — steelman B&B + PCA-8 control + matched-recall sweep
- kernel: search_bnb_skip — the STEELMAN. Centroid-distance order (the
effective nprobe ordering) + per-cluster LB-skip (correctness-safe in
any order, unlike the LB-order global break). The strongest cluster-level
B&B: if it can't beat tuned nprobe, the bound doesn't pay.
- pca: minimal power-iteration top-m PCA (no linalg dep) for the low-dim
control — projects real arxiv features to 8-d where the bound is tight.
- examples/ivf_pruning_sweep: 3 contenders share one index per nclusters
(plain nprobe / B&B LB-order / B&B steelman) x 2 regimes (128-d, PCA-8),
exact-regime pruning probe, matched-recall@0.95, frozen-gate verdict.
RESULT (n=20k & n=50k both): steelman = 1.00x evals vs nprobe in EVERY
cell, BOTH regimes. NO-GO. Mechanism is structural, not dimensional: the
LB bound only prunes FAR clusters that tuned nprobe already skips, so it's
redundant with nprobe's centroid-distance cutoff. Exact-prune fraction
scales correctly with dim (0-13% @128-d, 8-87% @PCA-8) => kernel sound;
the redundancy is fundamental. LB-ORDER (faithful BET-2 kernel) is strictly
WORSE (0.18-0.25x) — LB-ordering probes far large-radius clusters early.
* docs(bet4): ADR-205 — cluster-pruning vs plain IVF nprobe = structural NO-GO
Verdict: NO-GO (robust, structural). Steelman B&B (centroid order +
LB-skip) ties tuned nprobe at exactly 1.00x member-evals in every cell,
n=20k & n=50k, 128-d & PCA-8. Mechanism: the triangle-inequality bound
only prunes FAR clusters that tuned nprobe already skips => redundant with
nprobe's centroid-distance cutoff; win is structurally impossible, not
just hard in high-d. LB-order (faithful BET-2 kernel) strictly worse
(0.18-0.25x). Companion to ADR-199.
Honest deviation recorded: the pre-registered PCA-8 control expected a B&B
WIN (tight bound). It tied instead — the premise was false (tight bound
beats full-scan, not tuned nprobe). Control still valid: exact-prune
fraction scales correctly with dim (0-13% @128-d, 8-82% @PCA-8) => kernel
sound; it revealed the structural redundancy. Scoreboard 2 WINS / 4 KILLS.
* chore(bet4): lockfile for ruvector-bet4-ivf-bench workspace member
* docs(bet5): FROZEN pre-registration — PQ/IVFADC within-list pruning vs tuned nprobe
Opens the one lever ADR-205 left explicitly open (within-list PQ asymmetric
distance, orthogonal to the killed cluster-level bound). Frozen gate: PQ must
beat the cheaper of {plain full-L2, early-abandon exact-L2} nprobe by >=2x
full-L2-equivalent member-evals at recall@10=0.95 AND wall-clock, across
nclusters{64,256,1024} at >=1 scale N>=50k. Honest prior: ~55% win-at-scale,
named kill-paths = amortization crossover + concentration re-rank ceiling.
Stacked on feat/seprag-bet4-ivf-pruning to reuse ruvector-bet4-ivf-bench.
Thread #534.
* feat(bet5): M0 — PqIvf (IVFADC) kernel + early-abandon steelman + gate
PqIvf trains m sub-quantizers on the shared ruvector-rairs k-means substrate
(kmeans assignments ARE the PQ codes), encodes corpus to m-byte codes, and adds
search_adc_rerank (cheap ADC scan of nprobe lists + exact L2 re-rank of top-R)
plus search_adc_only (pure-ADC ceiling probe). AdcCost charges everything in one
honest unit: 256 (LUT) + adc_members*m/D + rerank*1 full-L2-equivalents.
BnBIvf gains search_nprobe_abandon = the early-abandon exact-L2 steelman
incumbent (user-confirmed verdict-setter), charged in dims_touched/D.
Gates (real 2k arxiv slice): PqIvf shares centroids w/ BnBIvf; PQ@full-rerank
exact (recall>=0.999); early-abandon exact vs full L2 (<0.001). 6 tests green,
clippy clean. Thread #534, BET5 pre-reg frozen at
|
||
|---|---|---|
| .. | ||
| data.rs | ||
| kernel.rs | ||
| lib.rs | ||
| oracle.rs | ||
| pca.rs | ||
| pq.rs | ||