What is incremental HNSW indexing, and why does it matter for upsert-heavy workloads?

Incremental HNSW indexing means adding new points to an existing graph without rebuilding the entire graph from scratch. In Qdrant this is achieved structurally through the segment model: new points are appended to a small, mutable segment, and when that segment reaches the indexing threshold the optimizer builds a graph over it. Existing segments are left alone, so their graphs are never rebuilt just because new points arrived. Over time the optimizer merges several small segments into a larger one, which does involve building a new graph over the merged data, but that is a consolidation step, not a per-write rebuild. The effect is that an upsert only costs a WAL append and an in-memory insert; the expensive graph construction is amortized over batches and done in the background.

The reason this matters for upsert-heavy workloads is that the naive alternative - inserting each new point directly into a single global HNSW graph - scales badly. Every insert would run a graph search and rewire edges, and as the graph grows the insert cost grows with it, so a sustained write rate would eventually be limited by the graph insertion throughput rather than by disk or CPU. With the segment model, the write path stays cheap regardless of total collection size, and the indexing work is decoupled from the write acknowledgement. That is what allows Qdrant to sustain high write rates on large collections. There is a second dimension to incremental indexing that is less visible: when a point is updated (same ID, new vector), the old version is tombstoned in its segment and the new version is written to the current mutable segment. This means a single logical point can temporarily exist in two segments, and the coordinator has to resolve which version is current during a query. The optimizer's vacuum step is what eventually removes the tombstoned version and reclaims the space.

The trade-off is write throughput against read complexity and storage amplification. Incremental indexing keeps writes cheap, but it means a collection can contain many segments with overlapping point IDs (due to updates), which increases fan-out and makes queries slightly more expensive until the optimizer consolidates. It also means deleted points consume disk and query time until they are vacuumed. The common mistake is assuming an upsert of an existing ID is a cheap in-place update. It is not - it is a tombstone plus a new write, and a high update rate on a small working set can cause significant storage amplification until the optimizer catches up. The second mistake is assuming that a collection always has one segment per shard. It does not; the segment count is an emergent property of the optimizer, and a high-churn collection can temporarily hold many small segments. The third mistake is confusing incremental indexing with the ability to change m or ef_construct without a rebuild. You cannot - those are baked into the graph, and changing them requires re-indexing the segments. Version note: the details of how new points are incorporated into existing graphs versus new segments, and the exact behavior of the optimizer's merge and vacuum steps, have changed across Qdrant releases. In some versions there is more incremental graph updating within a segment; in others the segment model dominates.

Version-dependent: the internal mechanism of incremental indexing has evolved. Some releases have experimented with directly updating existing graphs for new points rather than always creating a new segment, and the optimizer's merge and vacuum behavior has been tuned over time. If you are reasoning about a specific write-rate limit, benchmark the actual upsert throughput on your version and your hardware rather than assuming a general model.