Lazy remove() leaves surviving nodes unreachable: contains()=True but search() cannot find them

[titusz]

Summary

After remove() + add() churn, surviving nodes can become unreachable from the HNSW graph:
contains(key) returns True and get(key) returns the correct vector, but search() with that
key's exact vector (distance 0.0) never returns it. The damage persists across save()/load() —
it is baked into the serialized graph.

This is silent recall loss under any update-heavy workload. It was found in production
(the ISCC search aggregator at search.iscc.io, which re-adds ~183k entries as remove+add on every
restart), then isolated to the engine.

Metric-independent: reproduced with stock Hamming and Tanimoto as well as the fork's NPHD, so
it is not related to any of the fork's patches.

Reproduction

Pure usearch, stock MetricKind.Hamming, no fork-specific features:

"""remove()+add() churn makes surviving keys unreachable from the HNSW graph."""

import numpy as np
from usearch.index import Index, MetricKind, ScalarKind

N = 25_000
BATCH = 256
PROBE = 999_999
ATTEMPTS = 10


def make():
    return Index(ndim=256, metric=MetricKind.Hamming, dtype=ScalarKind.B1)


def attempt(rng):
    vecs = rng.integers(0, 256, size=(N, 32), dtype=np.uint8)
    pvec = rng.integers(0, 256, size=(1, 32), dtype=np.uint8)
    keys = np.arange(1, N + 1, dtype=np.uint64)

    index = make()
    index.add(keys, vecs)
    buf = index.save()  # save + load is part of the trigger

    index = make()
    index.load(buf)
    index.add(np.array([PROBE], dtype=np.uint64), pvec)

    def reachable():
        hits = index.search(pvec, 10)
        return PROBE in [int(k) for k in np.atleast_1d(hits.keys).ravel()]

    assert reachable(), "probe unreachable before any churn"

    for start in range(0, N, BATCH):
        bk = keys[start : start + BATCH]
        index.remove(bk)
        index.add(bk, vecs[start : start + BATCH])
        if (start // BATCH) % 10 == 9 and not reachable():
            return start + BATCH, index, pvec
    return None, index, pvec


rng = np.random.default_rng(1)
for i in range(ATTEMPTS):
    at, index, pvec = attempt(rng)
    if at is not None:
        print(f"attempt {i}: ORPHANED after {at:,} churn ops")
        print(f"  contains(probe) = {bool(index.contains(PROBE))}")
        got = np.asarray(index.get(PROBE), dtype=np.uint8).ravel()
        print(f"  get(probe) correct = {np.array_equal(got, pvec.ravel())}")
        print(f"  search(exact vector) finds it = False")
        print(f"  index size = {len(index)}")
        break
    print(f"attempt {i}: survived")
else:
    print(f"no orphan in {ATTEMPTS} attempts (nondeterministic; base rate ~1 in 8)")

Output:

attempt 0: ORPHANED after 23,040 churn ops
  contains(probe) = True
  get(probe) correct = True
  search(exact vector) finds it = False
  index size = 25001

It is nondeterministic — identical inputs and seed produce different outcomes across runs
(Hamming seed=1 orphaned in one run and survived a re-run), consistent with multithreaded HNSW
construction. Measured base rate on a fixed-input repro was 1 in 8 runs for a specific probe key.
Sampling 500 random keys per index after 25k churned adds showed ~0.2–0.4% orphaned.

Observed orphan points across metrics, all with the same harness:

metric	orphaned after
Hamming (stock)	15,360 churn ops
Tanimoto (stock)	10,240 churn ops
NPHD (fork)	12,800 churn ops

The first key added after load() is systematically the most susceptible.

Suspected mechanism

index_dense_gt::remove() is a lazy deletion: it stamps the slot with free_key_, pushes the slot
onto free_keys_, and drops the slot_lookup_ entry. It does not repair the inbound links
held by surviving nodes. A live node whose inbound links all ran through slots that were freed (and
later recycled by new add() calls) becomes unreachable from the entry point, while contains()
and get() keep working because they resolve through the key lookup rather than the graph.

Re-adding the same key relinks it, which is why the churned keys themselves stay reachable and
only bystander keys are lost.

Related: remove() does not update entry_slot_ when the entry node itself is removed.

Neither existing repair path helps

• remove(keys, compact=True) (which calls isolate()) does not fix it. Measured orphan
  rate 1/8 — identical to the 1/8 baseline — at ~70% higher cost (6.6s vs 3.9s mean for 25k churn
  ops). Consistent with the mechanism: isolate() prunes links pointing to removed nodes, but
  does not rebuild lost inbound links for surviving ones.
• compact() does not repair it either, and is separately broken — see the companion issue
  below.

The only reliable remedy we have found is rebuilding the index from the source of truth with a
single batch add().

What a fix might look like

Any of these would help, roughly in order of preference:

1. Repair inbound links of surviving neighbors when a slot is freed (correct but costly).
2. A working compact()/rebuild that provably restores reachability, exposed on the Python Index.
3. At minimum, a documented way to detect orphaned nodes (a reachability audit), so callers can
   trigger a rebuild instead of silently losing recall.

Environment

• usearch-iscc 2.24.5 (reports usearch.__version__ == 2.24.0)
• Python 3.12.0, Windows 10 x86_64
• Also observed on Linux/Docker in production

Companion issue

compact() returns another key's vector — see #9

Downstream tracking issue: iscc/iscc-usearch#30

[titusz]

Root-cause analysis and status

Confirmed the suspected mechanism by code inspection of index_dense_gt::remove() and the typed index's slot recycling:

• remove() is lazy: it stamps the slot with free_key_, queues it in free_keys_, and drops the lookup entry — inbound links of surviving neighbors are never repaired.
• When a later add() recycles a freed slot, the node's adjacency lists are rebuilt for the new vector, destroying the old outbound links. A surviving node whose inbound links all ran through recycled slots becomes unreachable from the entry point, while contains()/get() keep working through the key lookup. Re-adding the same key relinks it, which is why only bystander keys are lost.

Reproduced with the script above on a build that includes the v2.26 upstream hash-table fixes (tombstone reclamation, SplitMix64 key hashing): 2/10 attempts orphaned — consistent with the reported ~1-in-8 base rate. The defect is in the graph, not the key lookup, so none of the upstream 2.25/2.26 fixes address it; upstream has no delete-consolidation either.

One correction to the framing

A working compact() will not serve as a repair path. compact() renumbers slots and rewrites neighbor links verbatim — it preserves the (broken) link structure exactly. The get()-corruption in the companion issue #9 is fixed for the next release, but compact() remains a locality optimization, not a reachability repair.

Remedy and outlook

A true fix is delete-consolidation at remove-time (reconnect in-neighbors of removed nodes to their out-neighbors, FreshDiskANN-style). That requires reverse-link tracking or O(n·M) scans per removal batch and is not planned for the next release.

Reliable remedy today: rebuild from the source of truth with a fresh index and a single batch add(). For update-heavy workloads that periodically re-add a full corpus, replacing the remove()+add() churn with a fresh-index rebuild sidesteps the defect entirely and is typically faster than churning through every entry.

A reachability audit (unreachable_keys()-style BFS from the entry point) plus a remove/re-add repair loop is feasible (~80 lines in the C++ core; the needed internals are accessible) and will be reconsidered after the planned rebase onto upstream v2.26.