HnswIndex.remove: hiding points in a built HNSW index #126

What would you like to improve?

Thanks for merging #124, and for #125. With #125, an HNSW index can take new points without the original data, but it still has no way to remove one. txtai's rabitq backend now supports upserts and deletes for IVF (neuml/txtai#1304), and for HNSW it still has to raise on delete.

It would help to have a remove for HNSW like the one IVF has.

Any ideas? (optional)

I prototyped remove on a local study branch and measured two tombstones before proposing anything. Proposed API, mirroring IVF:

size_t HierarchicalNSW::remove(const PID* ids, size_t n);   // returns how many were newly removed

removed = index.remove(ids)

The two tombstones:

• +inf in f_add and f_add_ex, the IVF convention. It needs no format change and no extra check in the search loop. A removed node stays in the graph, but its estimate is +inf, so once the buffer is full the search never expands it, and the paths through it are lost.
• A deleted mark. I used the high bit of the stored cluster id. The search still walks through the node with its real estimate and only keeps it out of the results, like markDelete in hnswlib. It costs a mask and a check in the search loop.

Setup: M 16, ef_construction 200, 4·√n KMeans clusters, inner product on normalized vectors. Data: 100k synthetic vectors with 384 dimensions, and 69.5k HotpotQA passages embedded with Qwen3-Embedding-4B and truncated to 384 dimensions (1,000 held-out queries). Recall@10 is measured on the live points, against an index rebuilt without the removed points in the same run.

Recall@10 change with 30% of the points removed:

With 50% removed the gap at ef 10 grows: -0.165 against -0.299 at 8 bits, -0.155 against -0.246 at 4 bits. Neither tombstone ever returned a removed point (ef 10 to 200), and both always filled k results.

Even with the mark, recall falls at ef = k, because removed nodes take slots in a buffer of size ef. Searching with ef · points / live points fixes that. Same setup, in separate runs:

Each cell is the change at ef 10, then the change with the scaled ef, both against the rebuild at ef 10. Over 15 conditions (nbits 1, 4 and 8) the scaled ef stays within 0.010 of the rebuild, and above it in 13.

Compatibility and cost:

• Neither tombstone changes a file that has no removed points. A file with removed points under the mark is refused by the 0.5.1 wheel ("HNSW: invalid or truncated index file"), because load checks the cluster id against the number of clusters, so an old reader cannot bring removed points back. A file with +inf tombstones loads in 0.5.1 and the points stay hidden.
• Search speed with no removals, prototype against main (six interleaved rounds, one pinned core): medians 0.98 to 1.00 of main at nbits 1 and 4, ef 10 and 100, and every per-round ratio range includes 1.0. So the mask costs at most about 2%, within the noise.

Questions:

1. Which tombstone do you prefer? +inf keeps the IVF convention and the file readable by older versions. The mark keeps recall at low ef.
2. Should search scale ef by points / live points itself, or should callers do it, with the rule documented?
3. Should I build on main or on top of Add HNSW insertion after construction #125? remove does not depend on add, but both change hnsw.hpp and the bindings, so building on top of Add HNSW insertion after construction #125 would avoid conflicts. If the mark is masked inside get_clusterid_by_internalid, the reads Add HNSW insertion after construction #125 adds already go through it. With the mark, add would still link new points through removed ones, as hnswlib does. With +inf, a removed point scores +inf and would almost never be picked as a neighbour.

The prototype is a study branch with switches for both tombstones, so I would write the pull request from scratch, with tests in the same shape as #124, once you pick the design.