How Many Queries Pay for a Vector Index?

An approximate-nearest-neighbour benchmark usually starts after the expensive decision has already been made.

Build the index. Tune it. Run queries. Plot recall against throughput.

That is useful if the index already exists and will serve traffic forever. It is incomplete if the corpus is rebuilt every hour, queried twice, or discarded after a batch job. A faster search can still be the more expensive plan when it has to repay index construction first.

The distinction matters for retrieval-augmented generation, semantic search, recommendation, image lookup, and duplicate detection. A product catalogue serving requests all day can amortize a substantial index build. An hourly RAG refresh, an investigative notebook, or a one-off clustering job may never send enough queries to earn it back.

I included that build cost in the comparison.

I compared exact GPU brute force with IVF-Flat, two IVF-PQ compression levels, and CAGRA on an RTX PRO 4000 Blackwell SFF. I changed corpus size, dimensionality, query batch size, and recall target. Then, for every confirmed ANN operating point, I asked:

How many queries must this index serve before its build time is smaller than the GPU time it saves over exact search?

The largest search win was real: CAGRA was 76.5× faster than exact search for a batch of 1,024 queries over five million 128-dimensional vectors at confirmed recall@10 above 0.80.

But it needed about 45,000 queries to repay its 17.96-second build. At a 0.99 recall target, the selected IVF-Flat path was slower than exact search. At 384 and 768 dimensions, batching reversed a small single-query ANN win and made exact search decisively faster.

No single corpus size separated exact search from ANN. Corpus size, dimension, batch size, recall target, and query frequency all changed the choice.

ANN begins with an economic deficit. Search speed matters only after enough queries have accumulated to repay the build.

Counting the whole index lifecycle

The corpus was deterministic synthetic embedding data: unit-normalized vectors sampled around 4,096 Gaussian cluster centres. That creates neighbourhoods for ANN algorithms to recover without pretending these vectors came from a real model. Squared Euclidean distance produces the same ranking as cosine similarity after normalization.

The controlled matrix covered:

• 100,000, 1 million, and 5 million vectors at 128 dimensions;
• 1 million vectors at 384 and 768 dimensions;
• batches of 1, 32, 256, and 1,024 queries;
• recall@10 targets of 0.80, 0.90, 0.95, and 0.99; and
• cuVS brute force, IVF-Flat, compact IVF-PQ, balanced IVF-PQ, and CAGRA.

Exact neighbours were computed once with cuVS brute force and persisted as the correctness reference. Every approximate result was compared with that same answer.

The timing boundary matters. Corpus upload was measured separately and omitted from both resident alternatives. Build time stopped only after GPU synchronization. Search time covered one cuVS call through synchronization. Serialization was separate. Each accepted result came from three fresh process replications, with two warmups and five measured searches per replication.

I tuned parameters once, then confirmed the selected settings independently. Tuning required a 0.02 recall cushion. A target survived publication only when the minimum recall across all three confirmation builds still met it. Six measured settings failed that rule; they remain in a public controls table but do not support the conclusions below.

The complete companion in ramwise-examples contains the output-complete notebook, 90-row substantiated result table, six unconfirmed controls, tested harness, methodology, digest-pinned container, and exact Conda package specification.

The break-even equation was simple

For batch size B:

seconds saved per query = (exact batch seconds - ANN batch seconds) / B
break-even queries      = ANN build seconds / seconds saved per query

If ANN search was slower, it had no finite break-even point.

This is an elapsed-GPU-time definition, not a claim that every second has the same dollar value in production. I kept recall, build time, persisted index size, and whole-device memory as separate constraints. Combining them into one hand-tuned score would hide the decision instead of clarifying it.

CAGRA was strongest for batched, moderate-recall search

At 128 dimensions, CAGRA became the clear choice for batches when the recall target stopped short of the last fraction.

The speedup grew dramatically with corpus size. The amortization count did not fall in the same proportion because CAGRA’s graph also became more expensive to build.

At 5M vectors and batch 1,024, the ≥0.80 CAGRA setting took 5.406 ms against 413.608 ms for exact search: 76.5× faster. Its break-even was still 45,061 queries. At 1,000 QPS that is about 45 seconds. At 10 QPS it is 75 minutes. At 1 QPS it is more than twelve hours.

Query frequency does not alter the query-count break-even. It changes whether the corpus lives long enough to reach it.

Only finite break-even points appear here. An ANN setting slower than exact search has no point to plot.

This chart shows each family’s fastest substantiated batch-32 operating point, not one shared recall target. The recall-conditioned table above is the fairer decision view.

At 0.99 recall, brute force came back

At 1M×128 and batch 1,024, CAGRA held 0.986 minimum recall with a ≥0.95 target and ran in 8.283 ms. The setting selected for 0.99 was IVF-Flat probing all 1,024 lists. It returned exact recall, but took 286.937 ms—3.69× longer than brute force.

The same pattern held at 5M×128. The ≥0.95 CAGRA result ran in 12.648 ms. The 0.99 IVF-Flat result reached exact recall but took 1.936 seconds against 413.608 ms for brute force.

Approximation created the speed. When the recall target forced a partitioned index toward exhaustive work, its bookkeeping made it slower than the brute- force kernel it was meant to replace.

cuVS itself describes brute force as a valid choice for exact results and relatively small corpora—from thousands to a few million vectors—and notes that filtering can strengthen that case. My result extends the practical lesson: exact GPU search can also be the better high-recall baseline when ANN tuning removes most of the approximation.

Batching changed the algorithms differently

Batching helped CAGRA exploit parallel graph traversal. It did not help every index equally.

For 1M×128 at batch 32, CAGRA reached confirmed ≥0.90 recall in 0.456 ms versus 3.750 ms exact, an 8.22× win. At batch 1,024, the comparable CAGRA setting was 17.47× faster.

IVF-Flat behaved differently. The full-probe setting that supplied exact recall was slightly faster for one query at 384 and 768 dimensions:

The single-query wins amortized their builds after roughly 762 and 643 queries. For every larger tested batch, no finite break-even existed.

An index choice therefore belongs to the serving shape. “Queries per second” and “queries per call” are not interchangeable: a service can receive high QPS while still issuing batch-1 searches, or accumulate requests into batches and accept queueing delay.

IVF-PQ traded recall for memory

At 5M×128, the balanced IVF-PQ file was about 348 MiB. IVF-Flat was about 2.44 GiB and CAGRA about 3.58 GiB. Compression clearly worked.

Its recall ceiling was the problem. Balanced IVF-PQ produced only eight substantiated rows across the full study, all around the 0.80 class. Compact IVF-PQ produced none above the minimum target. Even when balanced IVF-PQ was faster than exact, CAGRA or IVF-Flat usually supplied a better speed/recall point.

For this synthetic distribution and these code sizes, product quantization offered much smaller persistence in exchange for a lower quality ceiling. A corpus that does not fit as float32 vectors may make that trade necessary even when another index has the better speed/recall frontier.

Choosing an index on this box

I would use four rules on this box:

1. Keep exact GPU search as the default for short-lived corpora, batch-1 work, and near-exact requirements. It has essentially no index build and remained competitive well into the million-vector range.
2. Use CAGRA for stable, repeatedly queried 128-dimensional corpora when 0.90–0.95 recall is acceptable. It was the strongest batched frontier, but I would require the expected lifetime query count to clear the measured 30K–46K build-amortization range.
3. Treat 0.99 as a new workload, not a slider adjustment. In this matrix it often pushed IVF-Flat toward exact work and erased the ANN advantage.
4. Choose IVF-PQ because memory requires it, then validate its quality on the real embeddings. Compression was substantial; the tested quality frontier was not.

The scope is warm resident data, one GPU, synthetic clustered embeddings, fixed cuVS 26.08.01 builds, and no vector database. I did not test metadata filters, network ingress, concurrency, updates, deletes, queueing, index restore, multi-GPU search, or an embedding model’s actual distribution. Whole-device memory was sampled with NVML; eleven of 90 public rows use an explicitly marked after-build fallback for at least one missing search-window sample.

Those limits define the next layer of testing, especially with real embeddings, metadata filters, and a serving queue. For the measured CAGRA points, the index became a net time saver only after roughly 30,000 to 46,000 queries. Exact GPU search was fast enough that index construction had to be justified by corpus lifetime and recall requirements, not treated as automatic preprocessing.

Sources and reproducibility

• Output-complete notebook, confirmed evidence, controls, and full harness
• cuVS exact brute-force guidance
• cuVS index selection primer
• cuVS Bench measurements and parameter tuning
• CAGRA paper
• cuVS IVF-PQ API and compression parameters