A recall smoke test is supposed to be boring. Build the index, run a fixed set of queries against it, check that each query gets back most of its true nearest neighbors, glance at the average, move on. In May one of those runs stopped being boring: on a 10,000 vector index at 384 dimensions, individual queries in the same run were landing anywhere from 25% recall to 87.5%.
Recall is the fraction of the true nearest neighbors a query actually gets back. The exact answer comes from brute force: score the query against every stored vector, no index in the way, keep the top k. Then ask the index the same question and count the overlap. Ask for the top eight, get two of the right ones, and you scored 25%. Brute force is slow, which is the reason the index exists at all, but it is exact, so it makes a clean yardstick. The fixture behind the test was small, 10,000 vectors of 384 dimensions each, the shape of a modest embedding corpus, with ground truth precomputed by that same brute-force pass.
I normally glance at the average, and this run's average would have passed that glance. The failure was only visible in the per-query spread.
An under-searched index fails evenly. Every query stops exploring a little too early, so every query drops a neighbor or two, and recall drifts a few points below target across the whole set. That is a tuning problem: raise the per-query search budget and the drift closes. A spread from 25% to 87.5% inside one run is a different failure. Same graph, same budget, and one query finds seven of its eight neighbors while another finds two.
An average blends those into something passable. The same mean can come from every query sitting a few points low or from half the queries doing fine while the other half fail structurally, and only the second one means the index is broken. The per-query view is what tells the two apart, and it is the view this test almost did not get looked at through.
If the structural reading was right, the queries at the bottom of that spread were not short on budget. The walk they were allowed to make never had the true neighbors ahead of it: the graph handed them a neighborhood, most of the vectors that actually sit closest were never reachable from inside it, and searching that neighborhood harder just re-ranks the wrong vectors.
So the spread pointed at construction, at how the graph was built rather than how hard it was being searched. I did not act on that directly, because the two readings ask for very different responses. If it was tuning, the fix was an afternoon of nudging defaults. If it was construction, everything downstream of the builder was suspect and the fix started at rebuilding the graph. I wanted one experiment whose outcome separated the two cleanly.
The 64x experiment
The experiment had two arms, reachability and cost, and it ran at the next scale up. At 100,000 vectors, same 384 dimensions, default settings, recall came in at 12.5%. In the top-eight illustration from earlier, 12.5% is one right neighbor in eight. That is not the even drift of an under-searched graph. Most queries were coming back with almost nothing.
The second half of the experiment asked whether the neighbors were reachable at all. Crank the per-query search budget to 64 times the default and re-run: recall came back to 100%. A budget that wide stops the walk being selective: the candidate pool covers so much of the graph that the search degenerates toward an exhaustive scan, and routing quality stops mattering. So the true neighbors were present and reachable. The graph was failing to route to them at any reasonable budget.
The other arm was cost. At the default budget these queries ran at 65 to 85 microseconds each. At 64x, 12.4 milliseconds each, about 176x the measured baseline. The index sits in a retrieval path whose useful operating range is tens of microseconds per query, the range the default budget was already in. 12.4 milliseconds per query is far outside it.
That run settled the diagnosis. Correctness was recoverable through search budget alone, and brute-forcing it cost far more than the problem was worth. So the problem lived in construction.
What the run did not say is where inside construction the defect lived. It localized the problem to the builder and ruled out the routes around it; the defect itself stayed unidentified.
Three probes before a rewrite
A ground-up rewrite of construction was the biggest job on the table, so before committing I checked whether smaller structural changes could close the gap. I took three ideas from a well-regarded reference implementation in this space. Borrowing beat inventing here for a plain reason: a reference implementation's choices have survived other people's data, and if one of them fixed 100k I would take it and move on.
Every probe ran at both scales, because the two scales were already disagreeing. 10k builds and runs fast enough to drive the iteration loop; 100k is where the graph had actually failed. A probe had to look good at both to survive.
The procedure was the same for all three. Apply the change to the existing construction path, measure, and keep the diff and the numbers whether the answer is yes or no, so a rejected direction stays checkable later.
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 keeps a bounded list of neighbor edges per layer, and that bound, the connectivity, is the main structural parameter a builder controls. It is also the parameter with the most direct cost attached: double a node's neighbor bound and its edge list doubles, and at level 0 that means the whole graph gets heavier, because level 0 is where every point lives.
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 looked fine: 93.75% recall, nothing alarming in latency. At 100k it fell apart: 50% recall, with latency worse on top. Whatever makes that convention work in its home codebase, it did not survive the jump in scale on this data, and a change that halves recall at the failing scale rules itself out. It also put down a marker for the rest of the week, 10k results were not predicting 100k results, and the remaining probes got read with that in mind.
Probe two: the fallback fill
When construction inserts a new point, it gathers a pool of nearby candidates and then selects which few become the point's neighbors. The standard selection heuristic prefers spread over raw closeness: a candidate is skipped when it sits closer to an already-chosen neighbor than to the new point, because edges that all cover the same direction are wasted edges. Downstream of that, implementations split on one detail. When the heuristic skips too many candidates and neighbor slots go unfilled, some run a fallback pass that fills the remaining slots from the skipped list; stricter ones leave the slots empty in the name of diversity. The strict version gets cleaner neighborhoods and leaves some nodes with fewer edges than their bound allows.
My construction path had the fallback fill, and the reference implementation's stricter mode drops it, so probe two removed it and left selection purely diversity-driven. At 10k recall held at 100%, and if I had measured only one scale, this probe would have shipped. At 100k it came in at about 97.27%. Against a 99% floor, a drop of nearly three points is a plain miss, so the fallback fill went back in. The conclusion I kept is deliberately narrow: the fallback fill is beneficial for the current fixture. A verdict tied to a fixture invites re-testing when the fixture changes, which is different from declaring the fallback good in general, and I only measured this fixture.
Probe three: a wider construction search
Construction searches the graph it is in the middle of building. To place a new point, the builder runs the same kind of search a query would run, over the graph as it exists so far, and the result becomes the candidate pool that neighbor selection draws from. That search has its own width parameter, separate from the query-time budget. Probe three widened the level-0 construction search by 1.5x, on the theory that better candidates at build time make a better-connected graph. The theory is not crazy: the candidate pool is the raw material neighbor selection works with, and a wider search at build time should hand every insertion closer, more useful candidates.
It went the other way on both axes. Recall regressed at 100k, and insertion got slower with it: p99 insertion latency, the time the slowest one percent of insertions take, went up by 1.39 milliseconds per record. Worse on the metric I was trying to fix and worse on a metric I was not even trading against. A change that loses on both axes at once leaves nothing to weigh, so probe three ended there.
What the probes settled
None of the three ideas is bad. They are documented, reasonable choices from a codebase plenty of people trust, presumably doing real work on the workloads it was tuned against. They did not transfer to this data distribution and this scale, and each one was measured at both scales before it was dropped.
What the probes settled was the rewrite decision. Three structural adjustments had gone in, each borrowed from a design that works somewhere, and none of them held the target at 100k. Lined up, the three verdicts read: fine at 10k, 50% at 100k; 100% at 10k, a missed floor at 100k; worse recall and slower insertion in the same run. The incremental path was closed off three separate ways, and the 64x run had already closed the pure tuning path before that, which left construction itself as the thing to replace.
The rewrite
So I rewrote the construction path from the ground up, HNSW-style, instead of continuing to adjust the one that was failing.
One thing I am deliberately not doing here is telling a root-cause story about the old graph. I replaced the construction path whole rather than pinning the defect first, and a diagnosis reconstructed now, with the old code gone, would be a guess. I would rather leave the gap than fill it with something plausible. What I can stand behind is what was measured: the old path scattered per-query recall at 10k and collapsed to 12.5% at 100k, three structural fixes failed to move it, and the only measured route back to correctness was the 64x budget the earlier run had already ruled out. The rewrite would be judged by the same yardstick, the same fixtures, recall against the same brute-force ground truth; only the construction path changed.
The rebuilt index is a two-stage design. Vectors are stored quantized to int8, one byte per dimension, and an optional rerank stage re-scores the final candidates in full float32. The int8 stage keeps distance arithmetic cheap and the working set small. The rerank stage exists because quantized distances are approximate: close enough to route by, not always close enough to order the last few candidates correctly.
Routing and final ordering are different jobs, and the design keeps them separate. At query time the pipeline reads in one line: walk the int8 graph, collect a candidate pool, optionally re-score that pool in float32, hand back the top k.
So the index everything below is measured on is the rebuilt one: an int8 graph for routing, an optional float32 pass for final ordering.
The ledger for that week reads 165 commits to one file, 74 in a single day. Each probe, accepted or rejected, kept its diff and its numbers.
The rebuilt graph passed the same brute-force yardstick that condemned the old one. It also raised the next question, what recall costs as the query budget changes, which needed a curve rather than one point. The old builder's root cause remains unknown.