Inserting into a giant HNSW graph is slow and contended. A tiny fresh segment absorbs writes cheaply, gets searched by brute force, and a background job folds it into the main index later.
Picture a library where every book is shelved into a precise Dewey location. If someone donates a book, finding its exact slot, sliding existing books over, and updating the catalog takes a librarian ten minutes per book. Now imagine a thousand donations arriving per minute. The fix is a donation cart parked at the front desk. New books drop into the cart immediately. When someone asks for a topic, the librarian checks the main shelves and also flips through the cart, which is small enough to skim. Overnight, a staff team files the cart into the shelves at their own pace. Vector databases do exactly this. The main HNSW graph is the shelves; the fresh segment is the cart; compaction is the overnight filing. The user gets fast writes, near-real-time visibility of new data, and the main index stays healthy.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
The segment-plus-compaction pattern is one of those vector database design choices that looks weird until you map it onto LSM-tree storage engines, at which point it becomes the obvious answer. The shape is: writes are easy to append, hard to integrate into a large structured index; reads need both fresh and historical data; background work bridges the gap.
This walkthrough explains why HNSW inserts are individually expensive, how brute-force scan on a small segment is cheap enough to be useful, how the query fan-out and result merge work, what compaction actually does, and where the design's costs show up operationally.
Mental model: the main HNSW index is the well-organized library shelves. The fresh segment is the donation cart at the front desk. Compaction is the overnight filing crew. Users see fast donations, can find recent books on the cart, and the shelves never get jammed.
Why a single HNSW insert is expensive
HNSW is a multi-layer graph. Inserting a new vector means picking the entry layer (sampled from a geometric distribution), searching from the top layer down for the nearest neighbors at each layer, taking write locks on those neighbors to update their adjacency lists, possibly running neighbor pruning to keep the graph degree bounded, and then writing the new node to disk or memory.
The ANN search at each layer is the same operation a query performs. On a 100M-vector graph, that is roughly 1-3 ms of CPU. The lock work adds contention with concurrent queries reading the same nodes. End-to-end, a single insert costs 2-5 ms of CPU and produces measurable query-side latency variance.
At target write throughputs of 10k inserts per second, this design saturates a 16-core box on writes alone. Worse, the lock contention does not scale linearly; readers and writers contending on the same neighbor nodes produce tail latency spikes that show up as p99 jitter in user-facing metrics.
The rational response is not to make individual inserts faster, but to batch and defer them. A small fresh segment is the staging area where writes land cheaply, queries can still see them, and the eventual integration into the main graph happens in larger, more efficient batches.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
Real products, models, and research that use this idea.
- Pinecone serverless decouples hot fresh segments from compacted index pods, so write traffic does not contend with query traffic on the main graph.
- Qdrant exposes segment-merge policies (segment_number, max_segment_size) so operators tune the compaction cadence to their write rate.
What an interviewer would ask next. Try answering before peeking at the approach.
QWhy do deletes also use the segment pattern, and what is a tombstone?
Removing a node from HNSW is as expensive as inserting one and breaks neighbor links. Engines instead write a tombstone, a metadata flag that excludes the vector at query time. Compaction physically purges tombstoned vectors when it rebuilds the segment.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Believing fresh writes go straight into the main HNSW graph. They almost never do at scale, because per-insert graph work would saturate the CPU long before write throughput hits target.
60 second bullets to scan on the way to the call.
Why HNSW inserts are expensive: ANN search per insert, neighbor locks, adjacency rewrites
Why brute-force scan on a small segment is fine: SIMD makes it microseconds
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.