[STORY] Research: HNSW orphan nodes on temporal shards — root-cause + remediation strategy

[jsbattig]

Type

Research / spike (investigation + strategy). NO implementation in this story — the deliverable is a documented recommendation the team signs off on before any code change.

Problem

check_hnsw_health reports orphan elements (nodes with 0 inbound connections) on temporal HNSW shards, e.g. code-indexer-temporal-voyage_context_4-2025Q2: Integrity Valid ✗ — Element 270/271/272/273 has no inbound connections (orphan). An orphan is reachable during ANN search only if it happens to be an entry point; otherwise it is unreachable, so those commits' vectors silently never surface in temporal queries. This is a recall dent, not corruption (Has Data ✓ — vectors are on disk and intact).

What is already understood (starting point — verify, don't assume)

• The integrity check is hnswlib's own checkIntegrity() (third_party/hnswlib/hnswlib/hnswalg.h:~1383-1407, assert(inbound_connections_num[i] > 0)); our fork only exposes it to Python (docs/hnswlib-custom-build.md). hnswlib itself defines a healthy graph as zero-orphan.
• Root cause is believed to be inherent to sequential HNSW construction: getNeighborsByHeuristic2 + M-bounded connection lists can prune a newly-inserted element out of ALL its chosen neighbors' lists, leaving it with outbound edges but zero inbound. The trailing IDs (270-273 = tail) are the fingerprint.
• Temporal shards are built one-shot at FilesystemVectorStore.end_indexing() (rebuild HNSW once — O(n²)→O(n)), NOT by ongoing incremental append (a past quarter has no new commits). But "one-shot" at our level is still sequential addPoint at hnswlib's level, so the tail-orphan mechanism applies to the one-shot build too.
• Likely NOT a defect in our build logic; likely NOT reliably fixable by a plain rebuild (rebuild re-runs the same sequential insertion and can reproduce orphans). Aggravated by clustered / near-duplicate per-commit vectors (0%-overlap voyage-context-4) and small shards.

Research questions (answer with evidence)

1. Parameters: What M / ef_construction do we pass when building temporal (and regular) HNSW indexes? Are they hnswlib defaults (M=16)? Do temporal and non-temporal differ?
2. Prevalence: Across staging (and a local corpus), how many shards have orphans, how many orphans each, and what fraction of elements? Is it correlated with shard size, embedder (voyage-context-4 vs embed-v4.0), or quarter?
3. Recall impact: Quantify the actual retrieval loss — do queries that should return an orphaned commit miss it? Build a small repro that inserts clustered vectors and measures orphan rate vs M/ef_construction.
4. Rebuild determinism: Does a full rebuild clear the orphans, reproduce them, or reshuffle them? Is insertion order deterministic (by point id) — and does shuffling help?
5. Deletions: Does the temporal refresh path ever delete+re-add points (mark_deleted/replace_deleted), which is a separate known orphan trigger? Confirm whether pure-append or delete-involved.
6. Health-check semantics: Is Integrity Valid ✗ the right severity for N orphans in an M-element shard? Should it be a graded WARNING (e.g. orphan-ratio threshold) rather than a hard failure?
7. Interrupted builds: Can an interrupted end_indexing() finalize leave a partially-linked graph (relevant: a staging index job was interrupted during this session)? Is finalize atomic / crash-safe?

Candidate strategies to evaluate (recommend one, with trade-offs)

• A. Tune build params — raise M and ef_construction for the temporal path; measure orphan rate vs. index size/build-time/query-latency cost.
• B. Post-build orphan-repair pass — after finalize, detect zero-inbound nodes and force back-edges from nearest neighbors (a bounded, deterministic repair).
• C. Insertion-order mitigation — shuffle / de-cluster insertion order for near-duplicate temporal vectors.
• D. Soften the health check — grade orphans by ratio; WARNING below a threshold, ERROR above; stop failing integrity on a handful in a small shard.
• E. Accept + document — if recall impact is negligible, document as a known HNSW property and lower the check severity.
  Likely a combination (e.g. A + D, or A + B).

Deliverable / Definition of Done

• A written findings doc (repro numbers for Q1-Q7) plus a recommended strategy with trade-offs and a proposed follow-up implementation story.
• No production code changes in THIS story (a tiny throwaway repro harness is fine).
• Reviewed/approved by the maintainer before spinning up the implementation story.

Severity / Priority

priority-3. Real (silent temporal-recall loss) but bounded (small fraction, approximate search); not corruption. Research-first to avoid a wrong fix (e.g. a rebuild that doesn't actually help).