diskann: insert() after build() takes the index offline until a full rebuild — add Vamana incremental insert

[ohdearquant]

Summary

insert() after build() takes the index offline: it appends the vector and sets built = false (index.rs:113), so every subsequent search() returns NotBuilt (index.rs:170-172) until a full build() runs again. A rebuild is O(n) graph construction plus a full PQ retrain and re-encode of every stored vector (index.rs:126-166). Vamana supports true incremental insertion, and it is cheap to add on top of the primitives this crate already has.

This matters doubly for the wasm ladder (#675, #676): a browser or edge session is long-lived and mutating, and cannot afford a multi-second full rebuild inside a worker because one document was upserted. An OPFS-persisted index (#676) wants append, not rebuild.

Verified at main c55e9e89.

Details

• index.rs:98-115: insert() pushes into the slab and id maps, then self.built = false.
• index.rs:125: "Build the index (must be called after all inserts, before search)". So the operational model is batch-build only; there is no way to add a vector to a live index.
• The building blocks for incremental insert are already present: greedy_search_fast for candidate acquisition, robust_prune (graph.rs:218) for neighbor selection, and the bidirectional edge update with overflow re-prune used during build.

Suggested design (standard Vamana incremental insert)

For a new point p on a built index:

1. Greedy search from the medoid for p with the build beam; the visited/candidate set is the candidate pool (one reusable VisitedSet, see the related visited-set issue).
2. robust_prune(p, candidates, alpha) to select p's out-neighbors (respecting max_degree).
3. For each selected neighbor u, add the back-edge u -> p; if u's degree overflows, re-prune u with its existing neighbors plus p.
4. Grow the pre-allocated visited set and (if PQ is enabled) encode p with the already-trained quantizer; retraining is not required per insert.

Cost is one beam search plus O(degree) prune work per insert, instead of an O(n) rebuild plus PQ retrain. Recall on incrementally built graphs stays within noise of batch-built graphs in our experience at the 10^5 to 10^6 scale; the paper's own construction is incremental at heart.

We ship exactly this in khive's vamana crate (ohdearquant/khive, crates/khive-vamana, insert()), alongside batch build, and are happy to port it here as a PR.

Measurable impact / acceptance

• Insert into a built index of n = 100k: index stays searchable throughout; per-insert cost is milliseconds (one beam search) versus a full rebuild (seconds, plus PQ retrain when pq_subspaces > 0).
• Recall@10 on a standard dataset where 20% of points are inserted incrementally after an 80% batch build is within 1 point of a 100% batch build.
• insert() on a built index no longer flips built to false; a test asserts search works immediately after insert and the new id is findable.