Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search: what it means for business leaders

A small table built offline predicts, before a vector search runs, which index configuration will return enough true neighbours for each query, and cuts retrieval cost to a median of 0.72 of a fixed configuration at the same service guarantee.

1. What the method is

The advance is a fidelity synopsis. It is a compact table, built offline, that estimates before any search runs how likely each candidate vector-index configuration is to return enough of a query's true nearest neighbours. Fidelity here means recall against exact search: the share of a query's exact top-k neighbours that a configuration actually returns. The synopsis divides the embedding space into cells around landmarks, which are cluster centres from spherical k-means on the corpus. For every cell and every configuration it stores the mean fidelity and a histogram of the fidelities seen on a sample of queries. At query time, one nearest-landmark lookup gives a calibrated probability for each configuration, and a selection rule picks the configuration so that the workload as a whole misses the target no more often than the operator allows. This is the histogram-and-optimizer method that relational databases use to estimate result sizes, applied to vector search.

2. Why the method was developed

Vector databases such as Milvus and pgvector pick one index configuration when a collection is indexed, usually tuned for average recall, and run every query on it. Queries differ widely in how hard they are to approximate, so that configuration is sized for the hardest queries within the reliability requirement, and every other query overpays. On the authors' benchmark, running each query on its cheapest sufficient configuration would cost about half as much as the static plan in a typical setting. For text-to-image search with SigLIP2 and OpenCLIP, about 89 to 90 percent of queries would meet the target on a configuration costing at most a third as much. Earlier per-query methods such as LAET and DARTH only decide when to stop a search inside an index already chosen, and DARTH assumes that index can reach the target. The most accurate HNSW setting reached fidelity 0.7 on only 69 percent of OpenCLIP image-to-text queries. Query-hardness scores exist, but they do not say which configuration will be enough.

3. Who should care

This matters to teams running retrieval at scale: search, recommendations, the retrieval layer behind our assistants, and multimodal catalog search where text queries retrieve images. Platform and infrastructure engineers would own the change. It means keeping several indexes or search settings live and adding a router in front of search, which adds memory and operational load. In this paper the HNSW indexes took 36 to 97 GB, against 2.5 to 24 GB for the compressed IVF variants. Finance and capacity planning care because the claim is lower cost at an unchanged, explicit guarantee: a fidelity target and a maximum share of queries allowed to miss it. Product owners get a sharper way to state retrieval quality than average recall. For the vector databases we buy, this is a feature to ask vendors for, since the paper finds none of them choose configurations per query. Small corpora served by one cheap index gain little.

4. How the method works

Offline, for each embedding model, the method picks landmarks per modality. It runs every query in a construction sample once through exact search and once through each configuration in the catalog, and records each configuration's fidelity. Each sample query goes to the cell of its nearest landmark. Per cell and configuration, it stores the mean fidelity and a histogram in bins 0.05 wide. From the histogram it reads coverage, the share of a cell's queries on which a configuration met a given target, so one synopsis serves any target. Cells with too few sample queries fall back to statistics from the whole sample. The table's size depends on the number of landmarks, the embedding dimension, the number of configurations and the number of bins, never on corpus size. Online, the query's nearest landmark is found, and the rule picks the configuration with the lowest cost plus a penalty times its estimated chance of missing the target. The penalty is tuned per target by five-fold cross-fitting. The choice depends only on the cell, so it can be precomputed.

5. How it was evaluated

The benchmark is 6,826,287 deduplicated LAION image-caption pairs, split 85, 10 and 5 percent into a 5,802,772-item indexed corpus, a 682,444-query construction sample and 341,071 held-out queries per setting. Four open-weight embedders were used: SigLIP2 at 1,152 dimensions, OpenCLIP ViT-L-14 at 768, and Jina-v4 and Qwen3-VL-Embedding-2B at 2,048. With four query directions (image or text, searching images or text), that gives 16 settings. The catalog has nine FAISS configurations: low, moderate and high tiers of HNSW, IVFPQ and rotation-optimized IVFPQ. Cost is mean latency on AMD EPYC 7763 servers, in batches of 4,096 queries on 64 threads, with indexes in memory. The default target is fidelity 0.7 on the top 100 results, with at most 10 percent of queries missing it. Baselines are the static plan, location-blind global estimates, a density-only estimate, a shared synopsis with one difficulty value per cell, two simpler selection rules and oracle optima. Our copy of the text cuts off after the estimation results.

6. How it performed

The estimates beat location-blind averages in all 16 settings. MSE skill ran from 0.32 to 0.59, within a few hundredths of the ceiling the cell partition allows. The coverage estimates were well calibrated, with AUC between 0.81 and 0.92 and calibration error below 0.006, and stable across clustering seeds. Keeping separate statistics per configuration beat one shared difficulty value per cell. The end-to-end results below come from the abstract and introduction, because our copy is truncated. Held to the same requirement as the static plan, selection was cheaper in all 16 settings, at a median of 0.72 of its cost. The batched lookup took 21 to 32 microseconds per query. The saving held against the best single configuration and within one index at no extra memory. That is well short of the roughly halved cost an oracle would reach. The authors name two limits: variation within a cell caps the saving, and single-query lookup is too slow for 2,048-dimensional models. All of this was measured on one dataset, on CPUs. Our call is to pilot it. (Source: arXiv 2610.41407, 2026)