SepRAG: CCH-inspired retrieval exploration + customizable re-weighting for self-learning ANN

[shaal]

Summary

Exploration of CCH-inspired hierarchical retrieval ("SepRAG") for RuVector's hybrid
vector + knowledge-graph memory, run as a disciplined, evidence-gated research thread. It
produced one negative result (recorded honestly) and one proven, shippable result.

This is a tracking/epic issue. The first deliverable (ADRs 196–200 + a reference crate +
six experiment harnesses) is in the companion PR. The remaining bets stay open below.

Measured impact (proven, with scope)

A new capability — adapt the ANN index to a changed relevance metric by re-weighting
the existing graph instead of rebuilding it. It does not change query latency or
absolute recall of existing search; it removes the rebuild cost a metric change otherwise
incurs.

• Update cost (metric change), reference Vamana: 141.8s → 0.035s at n=100k (~4,000×
  lower); ratio ~1,000–4,000× across n=5k–100k (rebuild is super-linear; re-weight ≈ a
  medoid recompute).
• Production ruvector-diskann Vamana (n=20k): rebuild ~7s → re-weight ~0.01s, recall
  within 2% of rebuild (96–99% absolute).
• Recall preserved: within 2% of full rebuild across diagonal / rotational / non-linear
  / region-local / compounding drift, up to n=100k.
• Hybrid operating point: re-weight every step + rebuild every ~4 → 98.8% vs 99.1%
  (always) / 94.4% (never), at 25% of rebuild cost.
• Not yet proven: drift is synthetic (parametric), not a live ruvector-gnn
  learned-metric trajectory; production-loop integration is backlog item Implement Ruvector high-performance vector database #1. No query-latency
  or recall improvement to existing search.

Motivation

Customizable Contraction Hierarchies (CCH) give ~35,000× speedups on road networks by
pre-processing a separator hierarchy. The question: can the same machinery (nested
dissection, separators, contraction shortcuts, elimination trees, separator-tree k-NN, and
metric-independent + customizable preprocessing) give large search-space reduction and
cheap self-learning re-weighting for embedding + KG retrieval?

Findings

❌ CCH full-contraction does NOT fit embedding retrieval (NO-GO, measured)

Validated implementation (ruvector-seprag, separator-tree k-NN == Dijkstra oracle on
toy + real graphs), then measured on real public data:

Backbone (n=1500)	blowup |G+|/|G_nav|	elim-tree height
roadNet-PA (control)	7.6×	~3.5·√n
ogbn-arxiv citation	23.8×	~0.6·n
ogbn-arxiv feature kNN	42.4×	~0.56·n

The road control proves the implementation is sound; both embedding-derived backbones are
intrinsically high-treewidth, so contraction blows up. HNSW already owns embedding kNN.
(ADR-199.)

✅ Customizable re-weighting (the salvaged idea) — proven WIN

Decoupled from CCH: in a self-learning store the metric drifts; instead of rebuilding the
ANN index, reuse the fixed topology and re-score under the new metric. Validated on the
production ruvector-diskann Vamana:

• Recall within 2% of a full rebuild across diagonal / rotational / non-linear /
  region-local / compounding drift, up to n=100k, at ~1,000–4,000× lower update cost.
• Hybrid operating policy: re-weight every step + rebuild every ~4 steps → 98.8% recall
  (vs 99.1% always-rebuild, 94.4% never) at 25% of the rebuild cost.
• Honest caveats: the recall gap widens with scale/churn (defer/batch rebuilds, not never);
  a drift-triggered rebuild monitor underperformed simple periodic (needs a better signal).

(ADR-200.)

Deliverables (companion PR)

• ADR-196…200 (docs/adr/) — the full decision record (one dead end + one win).
• docs/plans/seprag-cch-retrieval/ — milestone plans, FUTURE-DIRECTIONS.md (backlog +
  "prove-not-hype" protocol).
• crates/ruvector-seprag/ — reference CCH separator-tree k-NN + shared ANN engine +
  6 experiment harnesses (reweight_vs_rebuild, scale_drift, region_drift,
  diskann_drift, hybrid_policy, blowup_report). Tests + clippy green.

Backlog (open — same prove-not-hype protocol: one claim+number, beat a tuned in-repo

incumbent, public data, pre-registered win/kill gate, adversarial check)

• Productionize the win — wire "re-weight + periodic rebuild" into the
  ruvector-diskann/ruvector-gnn loop behind a flag, on a real learned-metric trajectory.
• Smarter rebuild trigger — sampled-recall probe vs the Frobenius monitor.
• BET 2 — filtered ANN (predicate-constrained) vs ruvector-acorn.
• BET 3 — multi-hop Graph-RAG on a sparse curated KG (HotpotQA / MuSiQue ground truth).
• BET 4 — region-pruning query on an IVF/clustering hierarchy (rairs-ivf, treewidth-immune).

Reproduce

Datasets are public (ogbn-arxiv, SNAP roadNet-PA). Each harness prints its pre-registered
gate. See docs/plans/seprag-cch-retrieval/FUTURE-DIRECTIONS.md for the protocol.

[shaal]

SepRAG scoreboard update — BET 2 ⊗ BET 4 resolved (qualified NO-GO)

BET 2 (filtered ANN vs ruvector-acorn) and BET 4 (region pruning on IVF) were run as one fused experiment (BET 4 = the mechanism, BET 2 = the benchmark/incumbent), pre-registered and executed under the prove-not-hype protocol. Writeup: ADR-201; code + finding: #536 (clearly marked as a finding, not a feature — no merge urgency).

Scoreboard

Bet	Status	Evidence
BET 1 — re-weight vs rebuild under metric drift	✅ WIN	ADR-200 (#535)
BET 2 ⊗ BET 4 — region-pruned IVF filtered ANN vs ACORN	⚠️ Qualified NO-GO	ADR-201 (#536)
BET 3 — multi-hop Graph-RAG on a sparse curated KG	⬜ Unexplored	—

Thread is now 1 WIN, 2 KILLS (ADR-199 CCH-on-embeddings, ADR-201 filtered-ANN) — the kills sharpened where the ideas work.

Why BET 2 ⊗ BET 4 is a NO-GO

Region-pruned IVF beats vanilla ACORN 6–48× (distance-evals) at selectivity ≤ 1%. But the pre-registered ≥5× WIN does not survive the adversarial check (rule #5): a predicate-aware-entry ACORN cuts its own cost ~18× at high correlation, collapsing the gap to ~2× (below the bar). A and predicate-seeded ACORN exploit the same structure and converge. Real but narrow edge remains at ρ≈0.7. Full detail in ADR-201.

Caveat worth recording

BET 4 was only partially exercised. The IVF region-pruning B&B kernel was built and validated exact (matches the brute-force oracle), but used only as BET 2's mechanism vs ACORN — never run against BET 4's original plain-IVF-probe baseline. The standalone "beats plain IVF" head-to-head is technically still open (lower priority given ADR-201's findings).

Follow-ups added to the backlog (ranked)

1. Multi-predicate conjunctions (highest-leverage new bet) — under X ∧ Y ∧ Z, cluster-skip composes while ACORN's predicate-aware seeding degrades sharply (a sampled seed satisfying all conjuncts is exponentially unlikely). The one regime where A could beat tuned ACORN even at high correlation. Reuses the new ruvector-filtered-bench harness.
2. Large-n re-test (n ≥ 10⁵–10⁶) — ACORN's predicate-aware seeding leans on a ~full predicate scan the distance-eval metric treats as free; at scale that's genuinely costly and may re-open A's edge.
3. Capitalize on BET 1 — wire re-weight + periodic-rebuild into the diskann/gnn loop behind a flag; validate on a real learned-GNN metric trajectory (ADR-200 next-steps). Highest overall EV if the goal is shipping value.
4. BET 3 — multi-hop Graph-RAG on a sparse, bounded-degree KG (the one backbone where the separator kernel — dead on high-treewidth embeddings, ADR-199 — could finally fit).

[shaal]

Correction to the backlog above. On closer scrutiny, the #1 follow-up I listed (multi-predicate conjunctions) does not hold and is retracted in ADR-201 (#536). A conjunction is a single O(1) boolean predicate of selectivity ≈ the product — in the distance-eval metric it reduces to (selectivity, geometric scatter), both axes already swept; ACORN's predicate-aware entry finds a conjunction-seed by sampling at exactly the rate of any equally-selective predicate. The "exponentially-unlikely seed" reasoning was wrong.

Residual BET 2 ⊗ BET 4 leads are narrow/speculative (predicate-evaluation-cost on a different cost axis; large-n where the free-predicate-scan assumption breaks). Recommend treating BET 2 ⊗ BET 4 as closed (qualified NO-GO). The thread's remaining value: (a) productionize BET 1 (the proven WIN, ADR-200) and (b) BET 3 (multi-hop KG, a different mechanism).

[shaal]

BET 1 productionized — WIN on a real learned-GNN trajectory → PR #537 (ADR-202)

Closed ADR-200's next-step #4. Wired the reuse-under-drift policy into the production ruvector-diskann loop behind a feature flag (reuse-under-drift, default off) and validated it on a genuine learned trajectory (contrastive link-prediction / InfoNCE over ogbn-arxiv citations) — not synthetic A(t) drift.

Result (gate pre-registered & frozen before any run):

• Pure topology reuse holds within 2% recall@10 of full rebuild up to a 40% top-10 churn ceiling — identical at n=20k and n=50k (≥ ADR-200's synthetic ~36%). Transfer confirmed.
• Periodic{k:4} recovers the high-churn tail to within 0.01% (20k) / above rebuild (50k) at 20–24% of rebuild cost, equal per-query work — ADR-200's hybrid reproduced on real drift.
• Stale control collapses 92%→33% (teeth). Honest caveat: pure reuse past the ceiling decays; the shippable policy is periodic, not never-rebuild.

Outcome: ADR-202. FUTURE-DIRECTIONS BET 1 open-item #2 (wire-into-loop) is now done; remaining open: live serving hook, sampled-recall trigger (ADR-200 #2), second learned objective, incremental-rebuild baseline.

[shaal]

Follow-up WIN — sampled-recall rebuild trigger (ADR-200 next-step #2) → added to PR #537

ADR-200's Frobenius drift-monitor had lost to fixed periodic; this re-tests a sampled-recall trigger under variable-rate (bursty) drift — the regime where a fixed cadence is provably suboptimal. Gate pre-registered + frozen before the run.

WIN (n=20k, bursty trajectory, 89% end churn): Recall{floor=0.95} = 97.2% recall@10 at 7 rebuilds, beating Periodic{k=2} (96.8% @ 12) on both axes (~42% fewer rebuilds) and the best Frobenius{τ} (97.3% @ 9) on rebuilds. Probe-cost trap passed (~1s probe vs ~73s rebuild saved). The trigger spends rebuilds right after bursts and skips calm stretches; its knob floor is the recall SLA (unlike k/τ).

Productionized as ruvector_diskann::reuse::RecallTrigger. Recorded as an ADR-202 addendum. Honest note: the first run was VOID (plain-SGD trajectory drifted 0%) — switched the generator to Adam and enforced the ≥15% churn precondition; the WIN/KILL gate was unchanged.

Remaining BET1 open: live serving hook; objective-dependence of the 40% ceiling (node-class fine-tune); incremental-rebuild baseline.

[shaal]

Generality check — ADR-202 holding ceiling CONFIRMED across a 2nd objective (+ an honest degeneracy caveat) → PR #537

Tested whether ADR-202's 40%-churn reuse holding ceiling is objective-dependent, using a second learned objective — node classification (real arxiv 40-class labels, CE on a linear head) instead of contrastive link-prediction. Same harness, contenders, 2% gate; only the objective changes. Gate pre-registered + frozen.

CONFIRM: node-class holding ceiling = 54% churn — above link-prediction's 40%. Reuse-vs-rebuild parity generalizes across two distinct learned objectives; the objective-dependence caveat is resolved.

Honest finding (not buried): past ~60% churn, node-class CE collapses the embeddings into ~40 class blobs where recall@10 becomes ill-posed (intra-blob near-ties; churn saturates at 67%, not 100%) and the full-rebuild baseline itself destabilizes (B swings 55–96%; a fresh Vamana build needs distance spread that collapsed geometry denies). So the trajectory-wide "reuse 92.1% > rebuild 87.8%" is a benchmark-degeneracy artifact (ADR-200's t=0.25 dip amplified), not a genuine reuse-beats-rebuild claim — reported as such. Operational conclusion unaffected: reuse + periodic is never worse here.

New open item: a collapse-aware quality metric for self-learning indices whose objective tightens clusters over time. ADR-202 addendum.

[shaal]

BET 3 resolved — curated KGs are high-treewidth → NO-GO (3rd KILL) → PR #538 (ADR-203)

The last untested backbone for the salvaged separator-tree kernel. Probed treewidth-first (cheap go/no-go gate) before building any multi-hop-QA harness — and it failed the gate, so the QA benchmark was (correctly) never built.

Scoreboard

Bet	Status	Evidence
BET 1 — re-weight vs rebuild under metric drift	✅ WIN	ADR-200/202 (#535, #537)
BET 2 ⊗ BET 4 — region-pruned IVF filtered ANN vs ACORN	⚠️ Qualified NO-GO	ADR-201 (#536)
BET 3 — multi-hop Graph-RAG on a sparse curated KG	❌ NO-GO	ADR-203 (#538)

Thread is now 1 WIN, 3 KILLS — the kills keep sharpening where the ideas work.

Why BET 3 is a NO-GO

Tested three real curated KGs spanning the spectrum, bracketed by the two calibrated controls in the same run:

Backbone	role	p (exp)	blow@ref(2k)	elim_h/n	tw lower bound
roadNet-PA	control	0.613	7.2×	0.04	tw ≥ 4
ogbn-arxiv	reference	1.259	17.4×	0.28	tw ≥ 44
WN18RR (WordNet)	KG	0.508	59.9×	0.21	tw ≥ 28
FB15k-237 (Freebase)	KG	—	42.3×	0.46	tw ≥ 42
CoDEx-L (Wikidata)	KG	1.826	5.1×	0.17	tw ≥ 28

• Structurally certain, not a heuristic artifact. The minor-min-width treewidth lower bounds (28–44) are 7–11× the road control's (4) — a lower bound guarantees treewidth is at least that large. This is the adversarial upgrade over ADR-199 (which leaned on the separator upper bound alone).
• Three different failure signatures, one gate that caught each. WN18RR: low exponent but huge absolute blowup. FB15k-237: near-linear elim_h. CoDEx: tree-like periphery (5.1×@2k) whose hub-dense core collapses treewidth (p=1.83) — a single-n blowup snapshot would have been a false GO; the pre-registered primary metric (scaling exponent) caught it.
• Root cause: every KG — WordNet, Freebase, Wikidata alike — is small-world with hubs (max degree 520/1999/4999 vs road's 9). Hubs kill separators regardless of average degree. Road-like low treewidth needs near-planar geometric locality, which no semantic graph has.

Combined with ADR-199 this closes the CCH-full-contraction line across five backbones (road, citation, two embedding manifolds, three KGs): there is no retrieval backbone of practical interest with road-like treewidth. The query kernel stays exact (recall 30/30 everywhere) and treewidth-independent — only contraction/build fails.

PR #538 is stacked on #535 (where ruvector-seprag lives); review only the 3 bet3 commits. No merge urgency — it's a finding.

Where the EV is now (ranked)

1. Capitalize on BET 1 (the proven WIN, ADR-202) — live serving hook into the ruvector-gnn embedding-flush path; collapse-aware quality metric. Highest remaining EV.
2. Separator-tree pruning kernel on a treewidth-immune IVF substrate — BET 4's standalone "beats plain IVF probe" head-to-head is still technically open (ADR-201).