recall@10 of single-vector search against a full scan is about 0.53 on 1M Cohere Wikipedia vectors #111

I ran firnflow 0.9.5 locally and built a recall@k harness. Two open issues here ask for this measurement:

• Multi-tenant load testing at 1,000+ namespaces #5, "Multi-tenant load testing at 1,000+ namespaces", under Considerations: "Include recall@k for indexed search versus flat scan. A latency win that costs recall is not a benchmark win."
• Add HNSW index type as an alternative to IVF_PQ #6, "Add HNSW index type as an alternative to IVF_PQ", under Considerations: "Include recall@k against a flat scan and the latency variance under filtered queries in any comparison benchmark."

Here is what the harness measures and what it found. The code is ready as a pull request; see the last section.

What the number means

There are two ways to answer "which rows are closest to this vector".

The first compares the query against every row in the table and keeps the ten closest. That is the correct answer by definition.

The second is the index. It searches only some of the partitions, and it stores each vector in a compressed form. Both shortcuts can change which rows come back.

Recall@10 counts how many of the index's ten results also appear in the exact top ten, divided by ten. A value of 1.0 means the index agreed with the exact scan. A value of 0.5 means half the rows it returned are not among the true ten nearest.

This is not the recall@10 in the BEIR reports under bench/results/. That one asks whether a human labelled a returned document relevant. An index can return a different relevant document, score well on relevance, and still return the wrong rows.

Setup

1,000,000 vectors from the Cohere Wikipedia dataset (CohereLabs/wikipedia-2023-11-embed-multilingual-v3, English split, at revision ade45fb5), 1024 dimensions, top 10. The embeddings ship pre-computed with the dataset, so a run needs no embedding model and no API key.

turbopuffer benchmarks itself on the same dataset at the same dimension and k:

• https://github.com/turbopuffer/tpuf-benchmark/blob/main/benchmarks/vector-knn-1m-hot.toml
• https://github.com/turbopuffer/tpuf-benchmark/blob/main/benchmarks/website/vector-10m-hot.toml

Rows went in through /import in batches of 10,000. I passed no index tuning options, so firnflow built its default IVF_PQ index. num_sub_vectors defaulted to dim / 16 = 64, which stores each 4,096-byte vector in 64 bytes.

Queries. 200 vectors taken from a shard I did not load into the table. A query vector that is also a row in the table will match itself. That inflates recall and makes the score meaningless.

Ground truth. For each query, exact distance against every loaded row, computed in NumPy, top ten kept. Vectors are unit-normalised on both sides, so the Euclidean ranking the server uses and the cosine ranking give the same order. No human labels anywhere.

Results

nprobes is the number of index partitions searched per query. The server default is 20, from DEFAULT_NPROBES in crates/firnflow-core/src/query.rs.

1,000,000-row namespace, 200 queries per row:

A separate 100-query run at the default scored 0.528, so the range across every run is 0.53 to 0.58. Treat the second decimal as noise at this sample size.

The default configuration returns about five of the true ten nearest rows.

Searching more of the index does not recover them

The obvious first guess is that the index looks at too small a slice. On a 100,000-row namespace, nprobes swept from 1 to 1000 in one pass, 200 queries per setting:

nprobes      1   recall@10 0.4625   p50 1.34 ms
nprobes      2   recall@10 0.5335   p50 1.50 ms
nprobes      5   recall@10 0.5715   p50 2.06 ms
nprobes     10   recall@10 0.5860   p50 2.95 ms
nprobes     20   recall@10 0.5870   p50 3.30 ms
nprobes     50   recall@10 0.5870   p50 3.32 ms
nprobes    100   recall@10 0.5870   p50 3.31 ms
nprobes    316   recall@10 0.5870   p50 3.32 ms
nprobes   1000   recall@10 0.5870   p50 3.32 ms

The low end is the control. Going from 1 to 2 partitions adds seven points of recall and costs more time, so the setting does take effect. Recall then stops at 10. The remaining hundred-fold increase changes neither recall nor latency.

An earlier run at the same corpus size, on an index build that no longer exists, gave the same shape at a higher level: 0.63 at one partition rising to 0.6945 at ten, then flat through 1000.

Per-query ids from that earlier run make it concrete. For the first query, all nine settings return the same ten rows. Rows 74773, 24462, 67843 and 62944 are among the true ten nearest and are returned at no setting at all.

Between two builds of the same index

An IVF index groups vectors into partitions using k-means, and k-means starts from centroids chosen at random, so recall moves between builds of identical data. Three consecutive builds of one unchanged 100,000-row namespace, each scored at the default nprobes of 20 over the same 200 queries:

build 1   recall@10 0.592   p50 3.41 ms
build 2   recall@10 0.595   p50 3.31 ms
build 3   recall@10 0.587   p50 3.33 ms

The spread is 0.8 percentage points. The gap this issue reports is around 40 points, so it does not depend on which build was measured.

What that rules out

The server is not silently falling back to a full scan at high nprobes. A full scan gives the exact answer, and recall is 0.587, not 1.0.

The missing rows are not being lost to a search that nprobes can widen. Four of the true ten are absent at every setting including the largest.

The remaining candidate is the compression. Each vector holds 4,096 bytes and the index stores it as 64 bytes. Distances computed from those 64 bytes are close enough to gather plausible candidates and too coarse to order them. nprobes chooses which candidates are considered, not how they are scored. Confirming this needs a re-scoring pass against the stored full-precision vectors, which this harness does not do.

One result I cannot explain from outside

num_partitions is documented in crates/firnflow-core/src/query.rs as defaulting to sqrt(row_count), which is 316 for the 100,000-row namespace. If nprobes 316 searched every partition, the low-end cost slope of about 0.18 ms per partition predicts roughly 57 ms. The measurement is 3.32 ms.

Either the partition count is far below the documented default, or nprobes stops taking effect somewhere above 10. Recall and latency both stop moving at the same point, which is what either would look like from outside. The nprobes_sweep_fiqa results already in this repository show the same flat response.

This does not change the conclusion above. Whatever nprobes 1000 does, it does not recover the missing rows. It does mean the sweep cannot be read as proof that the whole index was examined.

Limits

• One laptop (Apple M3 Pro, 18 GB RAM) running the server, MinIO and the harness together. MinIO on loopback, not a real object store. Latency is optimistic. Recall does not depend on the hardware.
• The server was built from a5f0a87 with one change: a Cargo.lock bump of ethnum 1.5.2 to 1.5.3. 1.5.2 does not compile on aarch64-apple-darwin, failing with error[E0512]. No source file was touched. Worth a separate issue if you want one.
• The million-row table was measured before the harness started recording result-cache hits, so its latency column has no zero-hit check behind it. The 100,000-row figures do carry that check. Recall is unaffected either way, because a cached result is the same result.
• One dataset. Two corpus sizes. One index configuration: nothing varies num_partitions, num_sub_vectors or num_bits. Three builds of that one configuration were measured.
• Single-vector namespaces only. Nothing here touches the multivector path.
• Single-client sequential queries. Not a throughput measurement.

The harness

It is on bench/single-vector-recall in my fork, open there as ekshaks/firnflow#2 with the full description and the raw JSON. I will open the same branch as a pull request against this repository, referencing this issue.

It adds no engine code. Nothing under crates/ or python/ is touched, so no existing caller is affected and neither Rust CI gate is involved.

Five changes you asked for after seeing an earlier version are in it: the dataset revision and per-shard checksums are pinned and verified; a second import into a populated namespace is refused; a sweep that the result cache answered fails instead of warning; and recall is reported across three index builds. The fifth, capturing the full test environment, is the one I have left for you, since you offered your own.

There is a follow-up change that moves the recall figure a long way. I would rather have the measurement agreed first.