diskann: trained PQ is never consulted at query time — wire PQ-guided search per ADR-144
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 4.5k
- Forks
- 603
- Avg merge
- 23h 32m
- Merged PRs (30d)
- 59
Description
Reading ruvector-diskann on current main (c55e9e89) 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 —
- At query time, build the per-query distance table (the flat
table[sub * 256 + code]layout already exists inpq.rs). - Greedy beam traversal scores hops via
pq_asymmetric_distance(O(M) table lookups per candidate instead of O(dim) mul-adds). - 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.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start in index.rs:133-145 and search() at 169-200, then read the query-table layout in pq.rs and pq_asymmetric_distance in distance.rs:170. Wire the existing PQ data into greedy traversal while preserving exact L2 re-ranking, and use the seeded recall harness in index.rs tests to compare recall@10 and latency.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- ai, search
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100