diskann: trained PQ is never consulted at query time — wire PQ-guided search per ADR-144

[ohdearquant]

Reading ruvector-diskann on current main (c55e9e8) with an eye toward contributing — the Vamana core is faithful to the paper (two-pass build, alpha-robust prune, medoid entry) and the recall harness holds up. One gap between ADR-144 and the code as wired:

ADR-144 says (Search section): "With PQ: filter candidates using approximate distance, then re-rank top results with exact L2."

What the code does today: build() trains the quantizer and encodes all vectors (index.rs:133-145), and save/load round-trip the codes (index.rs:261-274, 383-399) — but search() (index.rs:169-200) runs greedy_search on exact f32 vectors and re-ranks with exact L2. pq_asymmetric_distance (distance.rs:170) has no call sites in the query path. So configuring pq_subspaces > 0 today adds build time and memory without changing search behavior.

Proposal: wire PQ into the query path per the ADR's own design —

1. At query time, build the per-query distance table (the flat table[sub * 256 + code] layout already exists in pq.rs).
2. Greedy beam traversal scores hops via pq_asymmetric_distance (O(M) table lookups per candidate instead of O(dim) mul-adds).
3. Exact L2 re-rank of the final beam only — the code path search() already has.

No API change; the config knobs already exist. Beyond the per-hop speedup, PQ-guided traversal is the piece that decouples graph search from full-precision vector residency, which is what unlocks true larger-than-RAM serving (filing that separately).

We'd be glad to contribute this as an additive PR, with recall@10 and latency A/B numbers in the PR body — the seeded recall harness in index.rs tests makes it easy to keep that honest.

[ohdearquant]

Comment authored by an AI agent on behalf of @ohdearquant.

Follow-up on wiring the trained PQ codes into search() traversal: we implemented PQ-guided traversal with exact re-rank behind the existing pq_subspaces config (branch feat/diskann-pq-guided-search), measured it in two rounds against a pre-registered gate, and the honest outcome is that it does not clear the speed gate that motivates the feature, so we are not opening a PR. Posting the numbers so the trail is public.

Setup

N=100,000 random vectors, dim=128, k=10, Apple M2 Max, release build. Ground truth = exact brute-force top-10 over 50 sampled queries; latency = 20 warmup + 200 timed queries (round 2: 220-query shared pool). Same dataset/query seeds across all arms.

Pre-registered pass gate (fixed before running, from the round-1 exact-traversal baseline of recall@10 0.816 / median 695us / p95 2010us): recall@10 ≥ 0.80 AND median ≤ 417us (0.6× exact) AND p95 ≤ 2311.5us (1.15× exact), all simultaneously.

Round 1 — naive PQ-guided (full-beam re-rank)

Arm	Build	Recall@10	Median	p95
Exact traversal	840.7s	0.816	695us	2010us
PQ-guided (M=16, beam=64)	1264.1s	0.648	274us	2296us

Fast but recall-broken at defaults. A mutation check (corrupting the distance table collapses recall 0.900 → 0.030 on a small harness) confirmed the wiring is correct — the gap is approximation quality, not a bug.

Round 2 — query-time tuning sweep (one M=16 build, 3×3 cells)

Search-list width L × exact-re-rank pool R:

L	R	Recall@10	Median	p95
64	10	0.322	155us	462us
64	30	0.526	154us	458us
64	100	0.676	166us	1102us
128	10	0.330	274us	1962us
128	30	0.520	309us	2083us
128	100	0.740	265us	1353us
256	10	0.330	512us	1752us
256	30	0.512	386us	1022us
256	100	0.756	488us	2271us

No cell passes. Best cell (L=256, R=100, recall 0.756) was within 0.05 of the recall gate, which triggered the single pre-registered escalation arm — one M=32 rebuild at that cell:

Arm	Build	Recall@10	Median	p95
M=32, L=256, R=100	2843.8s	0.922	680us	2676us

Recall clears the gate decisively, but median (680us vs 417us) and p95 (2676us vs 2311.5us) both fail. Final verdict per pre-registration: no config clears; not opening the PR.

What we learned

1. The speed failure looks structural at dim=128. PQ steering saves exact-L2 work per hop but pays a distance-table lookup per neighbor. At M=16 the net win only shows up at recall-destroying beam widths; M=32 (needed for recall) doubles the table cost right back to exact-arm latency.
2. The surprising positive: M=32 PQ-guided + exact re-rank beats the exact-traversal recall ceiling at parity latency — 0.922 vs 0.816 recall@10 at 680us vs 695us median. The PQ-steered frontier explores differently than the exact greedy walk, and with a wide candidate pool plus exact re-rank it surfaces more true neighbors. So the trained codes may be worth activating as a recall feature at equal cost, rather than the speed feature framed here.
3. A revisit that targets the speed framing would need some combination of: OPQ-style rotation before quantization, SIMD-batched table scans, or admitting PQ distances only for frontier expansion while keeping exact distances for the result set.

Happy to share the harness details — the sweep is a single #[ignore]d test (bench_pq_tuning_sweep_100k) on the branch, fully reproducible from the seeds above.