Predict, then Probe

The instrument: one number, before you build

Everything on this page reduces to a single pre-flight measurement. Take a sample of your corpus (~4,000 documents is enough), a sample of real user queries (~100 is enough), embed both with the model you intend to use, and run exact brute-force search — no index, seconds of compute. Then:

q_plateau — "query plateau" — is a statistic we defined in this work; you won't find it in the ANN literature. It is the relative contrast that real queries see: for each query, the distance to its 10th-nearest document divided by the distance to its 50th, median over queries. A value near 1.0 means the 10th and 50th neighbors are nearly equidistant — the region around the answer is a plateau. A lower value means real gradient: the close neighbors are meaningfully closer than the crowd behind them.

Why does that number price search? Because graph search navigates by gradient — at each hop, the frontier keeps whatever got closer. On a plateau the frontier cannot tell progress from noise, so it must widen its beam to be safe, and you pay for that beam on every query, forever. Where distances fall off a cliff toward the true neighbors, the greedy walk locks on early and cheap. What taxes search is not corpus size, not closeness, not local dimensionality — it is the absence of a gradient.

Why believe one number? Because it was elected, not designed. A blind search scored 1,855 candidate formulas over a large feature battery against real-query serving cost on 119 corpus×encoder cells, with a shuffled-target null and a frozen exam on 72 cells collected only after the formulas were locked. The clever composite that won the first round degraded on the frozen exam (selection inflation — killed, as it should be). The single atom that held was q_plateau: ρ = 0.867 on never-seen cells, absolute serving cost predicted within 1.32× (median, held-out groups; 1.91× at p90). It is label-free, needs no index build, and — unlike the LID probe this page originally led with — it measures the causal quantity: interventions that move contrast move cost 5×; interventions that move LID alone move nothing (see the update in Finding 2).

import numpy as np

def q_plateau(X, Q):
    """X: (n,d) doc sample (~4k rows is enough); Q: (m,d) REAL user queries (~100+).
    Rows L2-normalized. Exact search on the sample -- no index, runs in seconds."""
    sim = np.sort(Q @ X.T, axis=1)[:, ::-1][:, :50]   # top-50 cosine sims per query
    d = np.sqrt(np.maximum(2 - 2 * sim, 0))           # -> Euclidean on the unit sphere
    return float(np.median(d[:, 9] / d[:, 49]))

Use real queries. Scoring documents against themselves flattered serving cost by 2× in this study's own verification incident (the league section), and systematically again in the follow-up. Comparing embedding models? Run the snippet once per model on the same text — the quotes are directly comparable, and the spread is routinely 2–7×.

import numpy as np

def probes(X, k=20, sample=1000, seed=42):
    """LID (Levina-Bickel MLE) + hubness skew, as used in the study.
    X: (n, d) float32, L2-normalized if your metric is cosine."""
    rng = np.random.default_rng(seed)
    idx = rng.choice(len(X), sample, replace=False)
    D = np.sqrt(np.maximum(
        ((X[idx]**2).sum(1)[:, None] + (X**2).sum(1)[None, :]
         - 2 * X[idx] @ X.T), 0))
    D[np.arange(sample), idx] = np.inf              # drop self-matches
    part = np.argpartition(D, 21, axis=1)[:, :21]
    nnd = np.sort(np.take_along_axis(D, part, 1), axis=1)
    lid = np.median(-1 / np.mean(
        np.log(np.maximum(nnd[:, :k-1], 1e-9) / nnd[:, k-1:k]), axis=1))
    occ = np.bincount(part[:, :10].ravel(), minlength=len(X)).astype(float)
    hub = ((occ - occ.mean())**3).mean() / (occ.std()**3 + 1e-12)
    return float(lid), float(hub)

The problem: everyone tunes on a slice

Here is how vector search actually gets tuned in practice. You take a sample of your corpus, maybe fifty thousand or a million vectors. You build an HNSW index, sweep the efSearch parameter until recall hits your target, note the settings, and ship. Then the corpus grows. Ten times. A hundred times.

The quiet assumption is that the settings you found on the slice still hold at scale. Every benchmark suite encourages this: ann-benchmarks runs at 1M, your production index is 50M, and nobody publishes the mapping between them. When I went looking for published validation that subset-tuned parameters survive scale, I could not find any. So I measured it.

The one-sentence version of what I found: sometimes the assumption holds perfectly, sometimes it costs you 4× your latency budget, and sometimes it fails completely. And you can tell which case you are in from the slice itself, in about thirty seconds.

Setup

The yardstick throughout is ef*: the smallest efSearch at which an HNSW index reaches 0.90 recall@10, on a reference build of M=16, efConstruction=200 (hnswlib). ef* is roughly proportional to per-query search cost, so "ef* doubled" reads as "same recall now costs about twice the compute."

I ran ef* ladders across nested slices, 50k up to the full corpus, on ten corpora chosen to vary the geometry, not just the size:

• sift-128 (image descriptors, the classic easy benchmark) and glove-100 (word vectors, the classic hostile one), to 1M;
• DEEP (96d CNN descriptors) to 10M;
• MS MARCO passages embedded by Qwen (1024d) to the full 8.84M, and the same passages embedded by Cohere v3 (1024d) to 6M. Same text, two models: a twin experiment;
• the same first 3M passages embedded by five more open models (MiniLM-L6, bge-small, e5-base, nomic-v1.5, bge-large), which I embedded myself on a rented RTX 3090.

Ground truth is exact brute-force nearest neighbors at every slice, and the pipeline is anchored: at the full 8.84M, my computed neighbors match the dataset's officially published ones with overlap 1.0000, both at k=10 and k=100. Total: 289 index builds, 3,320 measured sweep points, roughly $6.20 of rented compute plus two Macs. Details and caveats at the end.

Finding 1: scaling has regimes

Ask "what does 20× more data cost me at the same recall?" and the literature answer is a shrug plus "roughly log N." The measured answer is that corpora sort into three sharply different behaviors.

FLAT. MS MARCO embedded by Qwen needs ef*=20 at 50k vectors. At 200k: 20. At 1M, 3M, 6M, and the full 8,840,823: still 20. A 177× scale-up with zero increase in required search effort, and recall at ef=20 actually rises, 0.901 to 0.912. Subset tuning here is not approximately right, it is exactly right, and slightly conservative.

DRIFT. sift doubles (20 to 40 over 20×). The Cohere embedding doubles and then plateaus: 40 at 50k, 80 at 200k, and then 80 forever, confirmed out to 6M. DEEP quadruples over 200× (20 to 80 at 10M). Costly if unbudgeted, but bounded and well-behaved.

EXPLODE. glove needs ef*=160 at just 50k, 320 at 200k, and by 1M no setting in my sweep (up to ef=800) reaches 0.90 recall at the reference build. The bar has left the building. If you tuned glove on a subset and extrapolated, there is no ef you could have written down that survives.

Finding 2: a 30-second probe predicts the regime

Regimes would be trivia if you could only identify yours after building the full-scale index. The useful question is whether the small slices you already have contain the tell.

They do. Two cheap statistics, computed on a 1,000-point sample in seconds:

• LID, local intrinsic dimensionality (Levina-Bickel MLE, k=20): how high-dimensional the data behaves locally, regardless of its nominal dimension count.
• Hubness: the skewness of the "how often does each point appear in someone's top-10" distribution. High skew means a few hub points crowd everyone's neighbor lists, which strangles graph search.

The signature rule, fit by eye on the first five corpora:

Then the five league models arrived as a genuinely held-out test set, embedded after the rule was written down. Result: 9 of 10 corpora called correctly.

The miss is the most instructive point on the chart. MiniLM's LID rose by +0.24 and it stayed flat; bge-small's rose by a nearly identical +0.19 and it drifted. Within about ±0.3 of zero, the signal cannot resolve the outcome, and the honest move is to measure a bigger slice rather than trust the sign. Outside that dead zone the rule went a clean 8 for 8; inside it, one hit and one miss, which is exactly what a dead zone means.

Two more honesty notes. The probe predicts direction, not magnitude: it says "budget for drift," not "budget exactly 2.3×." And it works at the corpus level, not step by step: trying to predict each individual size-step transition from its LID delta only managed 58% across 206 transitions. The signal lives in the trend, not the increments.

Finding 3: the embedding league table

The twin result begged for a bigger version. So: take the same 3M MS MARCO passages, embed them with seven different models, and run the same ef* ladder on each. All seven now share the exact same passages via id-order prefix slicing, with the same index settings and the same ground-truth machinery — including Qwen, which I re-embedded myself after a verification pass (below) showed the pre-published file could not be trusted for this. The only variable is the model.

Serving the same passages at the same recall bar costs 2× more search effort under five of these models (ef*=80) than under the two cheapest (Qwen and MiniLM, ef*=40). That spread is invisible in every model comparison I have seen, because embedding models are compared on retrieval quality leaderboards and never on what they cost to serve at scale.

And quality does not rescue the expensive ones uniformly, because quality and serving cost are nearly inverted:

Finding 4: recall is a vanity metric

Everything above uses vector recall: did ANN return the same neighbors as exact search. But users do not want your exact-search neighbors, they want their answer. MS MARCO ships human relevance labels, so for each model I also measured MRR@10 and hit@10 against the labels, at every ef, alongside the exact-search ceiling computed on GPU.

By ef=40, every model delivers 96–99% of its exact-search answer quality (the re-embedded Qwen included: 98.8% of its MRR ceiling by ef=40, 99.5% by ef=80). By ef=80, 96–99% with vector recall still down at 0.90–0.95. Pushing ef from 80 to 640, an 8× increase in search cost, buys at most 0.6 points of MRR: chasing the last few recall points purchases almost nothing a user would notice.

The flourish: bge-small's ANN index at ef≥160 scored higher MRR than its own exact search (0.2661 vs 0.2652). Approximate search occasionally skips a "correct" nearest neighbor that was an unhelpful passage and surfaces a labeled-relevant one instead. The gap between vector recall and answer quality is not just slack, it can change sign.

Finding 5: one knob buys drift immunity

Drift is a 2–4× tax collected at deploy scale. It turns out you can pre-pay it, once, at build time.

Raising the graph degree from M=16 to M=32 (efConstruction 200) held ef* at or below 40 at maximum scale on every one of the seven drifting corpora: sift, DEEP over 200×, Cohere at both 3M and 6M, and all four drifting league models. On the flat corpora it matched or beat the reference (MiniLM: 40 down to 20). Only glove, the exploder, stayed out of reach, and the probe flags glove before you build anything.

M=32 costs you roughly 2× the index memory and a slower build. In exchange, the subset-tuned ef you measured on 50k stays approximately valid at 200× scale, on every geometry I tested short of glove. If your probe says DRIFT and you cannot afford a re-tune at deploy time, this is the knob.

The playbook

Methods and caveats

Corpora and scales. sift-128 and glove-100 (ann-benchmarks distributions) to 1M; DEEP 96d to 10M; MS MARCO v1 passages under Qwen 1024d (VIBE distribution, includes officially published exact neighbors) to the full 8,840,823; the same passages under Cohere embed-english-v3 to 6M; and the identical first 3M passages under MiniLM-L6, bge-small-en-v1.5, e5-base-v2, nomic-embed-text-v1.5, and bge-large-en-v1.5, embedded fp16 on a rented RTX 3090. Slices are id-order prefixes for the Cohere and self-embedded corpora, which makes those models' 3M slices the exact same text. The pre-published VIBE Qwen file turned out to store seeded-random subsets with passages standing in for queries (see the league section's update note), so I re-embedded the exact 3M prefix with Qwen-0.6B myself and evaluated it against real dev queries; the Qwen numbers here are from that clean run, not the file.

Index and sweep. hnswlib, L2 metric on unit-normalized vectors where the source is cosine/angular (rank-equivalent). Reference config M=16, efConstruction=200; grids up to M ∈ {8,16,32,48} × efC ∈ {100,200,400} at smaller scales, {16,32} × {100,200} at 3M+. efSearch swept over {10, 20, 40, 80, 120, 160, 240, 320, 480, 640, 800}; ef* is the first rung reaching 0.90 recall@10, so it is quantized to those rungs. 1,000 held-out queries per sweep.

Ground truth. Exact brute-force at every slice, validated end-to-end: at 8.84M my computed top-10 and top-100 match the officially published neighbors with overlap 1.0000. A variance gate (3 repeated builds) showed recall spread ≤0.14 points, so single builds are reported. One config was independently rebuilt on a second machine and architecture (Apple Silicon streaming build vs x86 bulk build) and landed on the same ef* with recall@20 within half a point (0.759 vs 0.764).

Answer-quality eval. MS MARCO dev queries with official qrels; within the 3M slice, 600 queries have their labeled passage present, so quality numbers carry a standard error around two points. MRR@10 and hit@10, k=10, at the reference build; exact-search ceilings computed by brute-force GPU matmul. Qwen now sits on the quality axis via the self-embedded run: exact hit@10 0.507 (second from the bottom), and ef*=40 under real queries — the pre-published file's ef*=20 came from scoring passages as their own queries.

The second study (the instrument upgrade, Aug 26–27). The q_plateau probe and the quote calculator come from a follow-up program on a separate testbed: 119 corpus×encoder cells — ten corpus styles (dialogue, Q&A, news, scientific abstracts, code, and several chunking constructions of a 369k-message personal-text corpus) under nine encoder families, 12.5k–353k documents per cell — each measured with real queries against exact ground truth. Same bar (recall@10 ≥ 0.90 at M=16/efC=200), finer ef ladder {10, 16, 24, 36, 54, 80, 120, 180, 270, 400, 600}, median of 3 builds. The formula search scored 1,855 candidate expressions (atoms, ratios, products, log-transforms over a geometry feature battery) against real-query ef*, disciplined three ways: a shuffled-target null (95th percentile of the best garbage formula over 60 permutations), leave-one-group-out stability, and a frozen exam on 72 cells collected only after the formulas were locked. The composite that won the first 46 cells degraded from ρ 0.842 to 0.705 on the frozen exam — selection inflation, killed. The single atom q_plateau held at ρ = 0.867 (leave-one-group-out minimum 0.834). The calculator's point estimate is a log-linear fit, log ef* = 43.08 · q_plateau − 37.61, across all 119 cells; the quoted error bands are the held-out-group calibration (1.32× median, 1.91× p90), not the in-sample fit. Fit domain: q_plateau 0.925–0.981. One out-of-family scale test so far: 3.1M arXiv abstracts under gte-base — predicted ~18, measured ef*=24 with zero build variance, inside the p90 band at 8.4× the size of the largest calibration cell, and cheaper to serve than a text corpus 8× smaller. The LID intervention: contrastive fine-tunes with a differentiable LID regularizer at four doses on identical data; LID fell 19% monotonically, hub-skew rose 2.14 → ~5× that, quality visibly degraded at the top dose — and ef* stayed 36 at every dose. The treatment is potent; the cost never moves; the correlation is a confound.

Honest limits. The signature rule was fit on five corpora and tested held-out on five more, all of which happened to be text embeddings of one corpus; more diverse held-out geometries would strengthen it. It predicts direction, not magnitude, and inside |ΔLID| < 0.3 it abstains (the dead zone is real: two corpora 0.05 apart went opposite ways). Per-step transition prediction is weak (58% over 206 transitions); use the corpus-level trend only. The q_plateau quote is calibrated on 12.5k–353k-document cells at M=16/efC=200 and k=10; it ranks reliably (ρ 0.867) but individual cells can beat the band — a handful of code corpora under mismatched encoders measured 2–3× their contrast prediction, which is why the calculator shows you the measured range of its nearest calibration cells rather than pretending the point estimate is exact. ef* speaks about search effort at fixed recall, not milliseconds: absolute QPS depends on hardware and I measured relative effort only. And the largest scale here is 10M; the 100M point is future work.

Cost. Roughly $6.20 of rented compute for the original study (a 64GB CPU box for the 8.84M anchor, an RTX 3090 box for the league embeds and GPU exact search) plus about $1.80 for the follow-up's rented grid cells, the rest on a Mac Studio and a MacBook Pro. Reproducing the headline findings needs one weekend and less than $10.