Sweeping the curve instead of picking a point_

After rebuilding Astral's graph, recall reached 99.22%. The cost was 8.80 milliseconds per query at the largest search budget I tested.

That one result passed the recall target, but it did not show whether the setting was efficient or fragile. I needed to see what each increase in search work bought, where the gains began to flatten, and whether a cheaper point could still hold the floor. So I measured the full recall-latency curve instead of choosing one passing point.

Sweeping the curve

The knob under the sweep is the query-time search budget, efSearch in HNSW vocabulary: the size of the candidate pool a query carries while it walks the graph. A wider pool abandons fewer directions early and touches more of the graph, which costs proportionally more time. I swept ten budgets at 100k on the rebuilt two-stage index, spaced finely enough that the features of the curve would actually show. Coarse spacing was the mistake to avoid: three points can straddle a knee without ever seeing it. Four of the ten points carry the story:

The first row is the bottom of the sweep, a budget of 512. The last row is the top of the sweep, a budget of 4096. The flattening starts just below the top: the 3840 budget, not shown in the table, repeats the third row's 98.8% recall at higher latency, about 8.4 milliseconds against 8.0. The middle rows are where the curve bends. Between the first two rows, roughly tripling the latency adds nearly 27 points of recall. Between the last two, 0.8 milliseconds adds less than half a point. The same parameter change lands very differently depending on where on the curve the setting already sits.

In plain terms: at the low end of the budget range, added budget moves recall by whole points. Near the target, the same increment moves it by fractions of a point, and at the top of the sweep it has nearly stopped moving it at all. That flattening is a finding on its own: just over 99% is where this graph tops out, and the residual is not reachable inside the swept range, which no single point could have shown.

This is also what the curve is for after the week ends. A threshold check returns pass or fail and nothing else. The curve answers the questions that come later: what the threshold costs in latency, and whether the operating point sits on a flat stretch or a steep one where the next data change moves it. Those answers get read off the curve instead of re-measured from scratch every time.

The floor I care about is 99% recall. On this graph, at this connectivity, it clears only at the top of the sweep: 99.22% recall at 8.80 milliseconds per query, on a budget of 4096. That latency was too high for the retrieval path this index serves. Fixing it meant leaning on the curve, and so far the curve had been measured at one scale only.

Diminishing returns at both scales

A curve measured at one scale can be an artifact of that scale, and this project had already burned me that way twice during the construction diagnosis: fixes that looked fine at 10k failed outright at 100k. So I ran the companion sweep at 10k on the same rebuilt design. The numbers live in different units, from 50% recall at about 34 microseconds to 100% somewhere between 539 and 684 microseconds. Both sweeps turn from steep gains to diminishing returns. That qualitative agreement is useful; it does not put the knee at the same normalized budget or latency.

That agreement was enough to trust the direction of the 100k curve, not to generalize its coordinates. On the broken graph, results at the two scales had disagreed every time they were compared. On the rebuilt one, both sweeps at least tell the same qualitative story: early budget buys large recall gains, then each increment buys less. The operating point still comes from the 100k fixture, in its own units.

The connectivity lever again

Clearing the 99% floor still cost 8.80 milliseconds per query, and the lever that brought it down had already failed me once. During the construction diagnosis, on the broken graph, I doubled connectivity at the base layer only, and at 100k it made everything worse: 50% recall, latency up. On the rebuilt graph I reached for connectivity again, this time doubling it uniformly across every layer, and this time it worked: with twice the edges under it, the query budget needed to hold the recall floor shrank about 2.7x, from 4096 down to 1536. It is worth being concrete about what shrank there. The recall stayed at the floor; what shrank is the amount of graph each query has to touch to get there.

Two things differ between those experiments. The earlier attempt changed the ratio between layers, giving level 0 twice the edges of the layers above; the retune kept the ratios and doubled everything. And between the two sits a rebuilt graph. The comparison is not controlled, so it does not isolate which difference mattered. The sentence I can stand behind is smaller: the same lever gave opposite verdicts because the graph underneath was a different graph, and a tuning result measured on a broken structure predicted nothing about the rebuilt one.

The documented starting point for 100k at 384 dimensions moved accordingly: from 32 neighbors, 64 build-time search, and 4096 query-time search, to 64 neighbors, 128 build-time search, and 1536 query-time search. Read as a pair, the triples say where the cost went, and it went in the cheap direction for this index: construction happens once per build, queries happen on every call. The graph carries twice the edges and construction searches twice as wide, so builds take longer and the index holds more memory. Every query for the life of that index then does about 2.7x less search work while still clearing the floor.

Budgets split by storage format

One more thing fell out of the sweep, and it needs the two-stage design from the rewrite: int8 storage doing the routing, an optional float32 rerank doing the final ordering. The two stages want different candidate pools. Routing needs the pool to contain the true neighbors somewhere in it; their positions inside the pool do not matter yet. The rerank stage re-scores the pool in float32 and reorders it, and reordering only helps if the pool was wide enough to contain what belongs at the top. So a format that reranks needs a wider pool than a format whose quantized scores are final. The routing job saturates early: once the true neighbors are somewhere in the pool, more pool is waste. Final ordering keeps improving for longer, because float32 keeps fixing ranks as long as better candidates keep arriving.

The defaults encode the split now: storage formats with a float32 rerank pass run with a 3x query-search-budget multiplier over plain quantized storage. Getting the split wrong fails in one of two directions: the plain format wastes search time refining an ordering its own arithmetic cannot improve, or the rerank pass gets starved of candidates worth reordering. So the search budget stopped being one number on the index and became a number per storage format, and a new storage format gets its default by being swept.

What the numbers are pinned to

Everything above is pinned to one fixture: 100k vectors, 384 dimensions, one data distribution, one machine. The latencies especially: 8.80 milliseconds at the top of the sweep says as much about my hardware as about the graph. The construction investigation already showed how badly numbers travel between two scales of the same fixture, and I extend that suspicion to my own defaults. 64 neighbors, 128 build search, 1536 query search is a measured starting point for this shape of data; anyone else's data needs its own sweep.

Two things stay open. Some queries still miss true neighbors at every measured budget, and I have not inspected what those queries share. The 10k sweep also flattened with added budget, but it did not predict the 100k coordinates or the earlier 100k construction failure. So the first million-vector fixture gets a fresh sweep; these runs do not tell me where its knee will sit.