One query found seven of its eight true neighbors. Another found only two. Both ran against the same 10,000-vector index with the same settings.
That score is recall: the overlap between the index result and an exact brute-force answer. On this 384-dimension fixture, per-query recall ranged from 25% to 87.5%.
The mean hid whether every query missed slightly or a few queries failed badly. I needed to distinguish them.
Query difficulty and local graph quality can both produce a wide spread.
If the low-recall queries only needed more search work, a larger budget should recover their neighbors. If the graph had built poor neighborhoods, searching harder would mostly rank the wrong candidates again.
The two explanations called for different fixes. A budget problem meant tuning the query. A construction problem meant rebuilding the graph. I tested the budget first.
The 64x experiment
I repeated the test at 100,000 vectors and 384 dimensions. With the default settings, recall fell to 12.5%. That is one correct result in eight.
At 64 times the default search budget, recall returned to 100%. I did not record visited-node counts, so I do not know how close the search came to scoring every vector. The neighbors were reachable, but only with an impractical budget.
Default queries took 65 to 85 microseconds. At 64x, each query took 12.4 milliseconds, about 176x the baseline. The retrieval path needed to stay in the tens of microseconds.
At 64x, recall returned, but each query took more than twelve milliseconds longer. Increasing the query budget was no longer useful, so I moved on to graph construction.
Three probes before a rewrite
Before rewriting the builder, I compared it with an established HNSW implementation. I tested doubled level-zero connectivity, strict diversity selection without fallback fill, and a wider construction search at both 10k and 100k. I would keep a change only if it improved both scales.
Probe one: connectivity at the base layer
An HNSW-style graph is built in layers. The upper layers hold a thinning sample of the points and work as an express network: a query enters at the top, and each layer hands it a better starting point for the layer below. The bottom layer, level 0, holds every point, and the final neighborhood search happens there.
Each node has a limit on neighbor edges per layer. That limit is the graph's connectivity. Doubling it doubles each edge list, and level 0 contains every point.
A common convention gives level 0 roughly double the connectivity of the layers above, on the reasoning that routing needs few edges and the final approach needs many. Probe one applied that convention. At 10k it still missed the 99% floor at 93.75%. At 100k it fell to 50% recall and latency also worsened. Whatever makes that convention work elsewhere, it did not survive the jump in scale on this data. It also established that 10k results were not predicting 100k results, so I read the remaining probes at both scales.
Probe two: the fallback fill
When construction inserts a point, it gathers nearby candidates and selects its neighbors. The usual heuristic favors spread over raw closeness. It skips a candidate when that candidate sits closer to an existing neighbor than to the new point, avoiding several edges in the same direction.
Implementations differ when this leaves neighbor slots empty. Some fill them from the skipped candidates. Stricter versions leave them empty to preserve diversity, giving some nodes fewer edges than their limit allows.
My construction path had the fallback fill, while the reference implementation's stricter mode drops it. Probe two removed the fill and left selection purely diversity-driven. Recall held at 100% for 10k records, but fell to about 97.27% at 100k, below the 99% requirement. The fill went back in. It helps on this fixture and should be retested when the fixture changes.
Probe three: a wider construction search
Construction searches the graph it is in the middle of building. To place a new point, the builder searches the graph as it exists so far, and that result becomes the candidate pool for neighbor selection. This width is separate from the query-time budget. Probe three widened the level-zero construction search by 1.5x. My hypothesis was that a wider build-time candidate pool would give neighbor selection closer candidates and improve connectivity at 100k.
Recall regressed at 100,000 vectors, and p99 insertion latency rose by 1.39 milliseconds per record. The change made both results worse, so I stopped there.
None of the probes held at scale
All three changes are reasonable HNSW choices. None met the target on this data at 100,000 vectors.
The first fell to 50% recall at 100,000. The second passed at 10,000 and missed the requirement at 100,000. The third reduced recall and slowed insertion. I stopped all three because none fixed the rebuild error.
The rebuild bug
The rebuild cleared every neighbor count, but it left the index's visible record count at its final value while reconnecting the first record. Construction could therefore search records whose graph edges had not been rebuilt yet.
I changed the rebuild to expose the population incrementally. It starts with a visible count of zero, increments that count immediately before reconnecting each record, and restores the final count when construction finishes. Rebuilding now presents the same sequence of graph states as inserting the records one at a time.
With that fix, the rebuilt graph reached 99.22% recall at an efSearch budget of 4096 in the recall-latency sweep. That point took 8.80 milliseconds per query, so it established that the graph could return the right neighbors but was not the operating point I wanted.
I later doubled connectivity across every layer and widened construction search. The current high-recall starting point for this 100,000 by 384 q8+f32 fixture is 64 neighbors, a build search of 128, and a query search of 1536.