Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search Adithya Ramanatha

Sanskar S. Singh

Maya Ramanath

NIT Calicut Calicut, India adithyar2115@gmail.com

IIT Delhi New Delhi, India ssanskar2705@gmail.com

IIT Delhi New Delhi, India ramanath@cse.iitd.ac.in

arXiv:2610.41407v1 [cs.DB] 30 Oct 2026

ABSTRACT Vector search has become a database operator with many physical implementations: different index families, build-time and searchtime parameters, and compressed or disk-resident variants. Each trades cost against fidelity, the fraction of a query’s exact top-𝑘 nearest neighbors that a configuration returns. Deployments nevertheless choose one configuration offline and use it for every query, so they are sized for their hardest queries and overpay for the rest. On a 5.8M-item LAION benchmark with four embedding models, running each query on the cheapest configuration that suffices for it would roughly halve the cost in a typical setting. Exploiting this requires predicting each configuration’s fidelity before running it, which is hard because fidelity is defined by the very exact search that approximate indexes avoid. Relational optimizers solve the analogous problem for cardinality with offline synopses; we propose one for vector search. A fidelity synopsis divides the embedding space into cells around a set of landmarks and records, for every cell and configuration, how often that configuration met a fidelity target on a sample of queries. At query time, one nearest-landmark lookup yields a calibrated estimate for every configuration, and an optimizer chooses configurations so that the workload misses the target no more often than its requirement allows. We test the two premises the synopsis relies on, that fidelity varies smoothly across the embedding space and that its loss is specific to each configuration. Held to the same requirement a static deployment is built to meet, synopsis-guided selection lowers cost in all 16 combinations of model and query direction, to a median of 0.72× the static deployment, with a batched lookup of 21–32 𝜇s per query. The saving persists against the best static choice among the same indexes, and within a single index at no extra memory.

1

INTRODUCTION

Dense vector representations have become the common currency of search. Text retrievers such as DPR [21] and ColBERT [22] map queries and documents into a shared embedding space, and contrastive vision–language models such as CLIP [38] and SigLIP [49], together with more recent multimodal embedders [28, 47], do the same across images, text, and visually rich documents, so that a text query can retrieve images and vice versa. In all of these settings, answering a query means finding its nearest neighbors in a large collection of vectors. Exact search compares the query with every vector and quickly becomes too slow; approximate nearestneighbor (ANN) indexes such as HNSW [32], IVFPQ [9, 17], and O-IVFPQ [11] return most of the true neighbors at a fraction of the cost. The same indexes underpin retrieval-augmented generation [26].

Queries whose cheapest sufficient plan costs Model (text→image) Jina-v4 Qwen3-VL SigLIP2 OpenCLIP

Optimum

≤ 0.33×

0.33–1×

1×

> 1×

none

cost

58.3% 76.8% 89.7% 88.8%

25.7% 0.0% 0.0% 0.0%

10.1% 18.2% 7.7% 9.6%

1.2% 3.6% 1.6% 1.5%

4.7% 1.4% 1.0% 0.1%

0.41× 0.39× 0.21× 0.20×

Table 1: Text-to-image search at a fidelity target of 0.7 on 5.8M LAION items, with all costs relative to the static plan. Left: held-out queries by the cost of their cheapest sufficient configuration (bold: at most a third of the static plan; none: no configuration meets the target). Right: the mean cost if every query ran on its cheapest sufficient configuration.

Vector search has consequently moved into database systems. Purpose-built vector databases such as Milvus [43], analytical engines such as AnalyticDB-V [46], and extensions such as pgvector [1] for PostgreSQL treat similarity search as a query operator; VBase [50] and ACORN [37] study how it composes with relational predicates, and [35] surveys the landscape. These systems offer many physical implementations of the same operator: a collection can be indexed with different index families, each with build-time parameters (graph degree, number of partitions, code length) and search-time parameters (efSearch for HNSW, nprobe for IVF indexes), kept in memory or compressed and placed on disk [8, 24]. Each choice trades latency, memory, and energy against fidelity, the fraction of a query’s exact top-𝑘 nearest neighbors that the chosen configuration (an index family with its parameter values) actually returns. Semantic query processing systems such as LOTUS [36] and Palimpzest [30] go further and compose retrieval with LLM-based filters, maps, and joins in declarative pipelines that are optimized for cost and quality; related systems process multimodal data under accuracy budgets [18] or optimize document-processing pipelines [41]. In these systems and in vector databases alike, however, the vectorsearch operator itself is executed in one fixed way. A configuration is chosen when the collection is indexed, typically by tuning for average recall on a sample workload, and every query then runs under it. The search-time parameters are exposed, but as sessionor collection-level settings; no component chooses them per query. In relational terms, the operator has several access paths but no optimizer that chooses among them. A fixed configuration is costly because queries differ in how hard they are to approximate. To measure this, we indexed 5.8M LAION image–caption pairs [39] under four embedding models and nine configurations of three index families, and recorded, for every held-out query, which configurations reach a given fidelity.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

OFFLINE · once per embedding model Sample queries 𝑄

Fidelity synopsis

Fidelity labels 𝐹@𝑘(𝑞, 𝐴𝑗) via exact k-NN

⋯ ⋯

⋮

corpus 𝐶

Landmarks 𝑙1…𝑙𝐾 (spherical k-means)

⋮

⋮

⋮

⋮

⋯

𝐾 × 𝑚 cells

landmarks synopsis read at query time

ONLINE · per query User query 𝑞∗

Nearest landmark 𝑙(𝑞∗), 𝑂(𝐾) scan

Budget rule, row 𝑙(𝑞∗)

min𝑗 𝑐𝑗 + 𝜆(1 − 𝜋̂𝑗) at most 1 − 𝜌 misses

run 𝐴𝑗

top-𝑘 results

No exact k-NN online. Added cost: one 𝑂(𝐾) scan per query.

Notation 𝐴1…𝐴𝑚 𝑘 𝜏 𝜌

𝑚 candidate indexes results per query (top-𝑘) fidelity target reliability level

𝐹@𝑘(𝑞, 𝐴𝑗) 𝜋̂𝑗 𝑐𝑗 𝜆

fidelity vs. exact k-NN Pr(𝐹@𝑘 ≥ 𝜏) in row 𝑙(𝑞∗) cost of 𝐴𝑗 price of a miss, tuned on 𝑄

Figure 1: Overview of the fidelity synopsis. Offline (top), a sample of queries is labeled with the fidelity of every configuration, and the labels are summarized per cell and configuration. Online (bottom), a query is located in its cell, and the budget rule uses that cell’s statistics to choose the configuration that runs it.

Our approach. Relational optimizers face the same problem when choosing among access paths: they estimate each plan’s output size from synopses, such as histograms, that are built offline and consulted at plan time. We propose such a synopsis for vector search, which we call a fidelity synopsis (Figure 1). It divides the embedding space into cells around a set of landmarks, representative points obtained by clustering the corpus. Offline, a sample of queries is run once through exact search and through every configuration in the catalog, and for every pair of cell and configuration the synopsis records the distribution of fidelity among the sample queries in that cell. At query time, the query’s nearest landmark identifies its cell, and the synopsis gives, for every configuration at once, the estimated probability that it meets the fidelity target, before any configuration is run. An optimizer then runs each query on a cheap configuration where that probability is high and on a more reliable one where it is low, so that the workload as a whole misses the target no more often than its requirement allows. Exact search is paid once, offline, on the sample. The synopsis rests on two premises, which we state and test rather than assume. The first is smoothness: fidelity varies slowly enough across the embedding space that a cell’s statistics represent the queries that fall into it. The second is configuration specificity: how the local geometry of the data translates into lost fidelity differs between index families, since graph navigation and quantization fail in different ways, so the synopsis must keep separate statistics for every configuration. Contributions. This paper makes the following contributions.

Table 1 shows text-to-image search at a fidelity target of 0.7. A static plan, the cheapest configuration that meets the target on at least 90% of queries, must be provisioned for the hardest of those queries. Yet for every model, most queries would meet the target on a configuration costing at most a third as much, and running each query on the cheapest configuration that suffices for it would cost less than half as much as the static plan. Early-termination methods address part of this problem. LAET [27] learns to predict, per query, when a search can stop, and DARTH [5] terminates each search once a declared target recall is predicted to be met. Both adapt how long a search runs within an index that has already been chosen, and both can only stop a search early: they cannot help when the chosen index cannot reach the target at all, and DARTH explicitly assumes that it can. In our measurements this assumption often fails. Even the most accurate HNSW configuration in our catalog reaches a fidelity of 0.7 on only 69% of OpenCLIP image-to-text queries, and for some text-to-image queries no configuration reaches it at all (Table 1, column “none”), consistent with the observation that cross-modal queries fall outside the distribution an index is built over [7, 29]. Measures of query hardness, such as local intrinsic dimensionality [4] and Steinerhardness [45], describe how difficult a query is, but they are not calibrated estimates of fidelity under a specific configuration and cannot tell an optimizer which configuration will suffice. What is missing is a way to predict, before running anything, how each candidate configuration will perform on a given query. This is hard for a basic reason: fidelity is defined relative to the exact top-𝑘, which is precisely what approximate indexes exist to avoid computing.

• We identify per-query choice of ANN configuration as an optimization opportunity and quantify it across four embedding models, nine configurations, and four combinations of query and corpus modality: serving the same queries as a static plan, the per-query optimum costs a median of about half as much (Section 5.1). • We cast pre-execution fidelity estimation as the vectorsearch analogue of cardinality estimation and propose the fidelity synopsis, which stores 𝑂 (𝐾 (𝑑 + 𝑚𝐵)) numbers for 𝐾 landmarks in 𝑑 dimensions, 𝑚 configurations, and 𝐵 histogram bins, together with a selection rule that holds the workload’s violation rate to a requirement (Section 3). • We test the synopsis’s two premises directly. A query’s cell predicts its fidelity in every setting, the synopsis’s estimate of how often a configuration meets the target is well calibrated, and keeping statistics per configuration beats a single difficulty value per cell for every model and index family (Sections 5.2 and 5.3). • We show that, under the same requirement a static plan is built to meet, synopsis-guided selection is cheaper in all 16 settings, at a median of 0.72× the static plan; that the saving persists against the best static choice among the same indexes and within a single index at no extra memory; and where its limits lie: variation within cells caps the saving, and a single-query lookup by exact landmark scan is too slow for 2,048-dimensional models (Sections 5.4 and 5.5).

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

Section 2 defines fidelity and the plan-selection problem, Section 3 presents the fidelity synopsis, Section 4 describes the evaluation setup, Section 5 answers five research questions, Section 6 discusses related work, and Section 7 concludes.

2

PRELIMINARIES

This section fixes the setting and notation, defines fidelity, and states the plan-selection problem. Table 2 summarizes the notation.

2.1

Corpus, Models, and Queries

A corpus 𝐶 is a collection of items, each an image, a text, or both. An embedding model 𝑀 maps items and queries of either modality into a shared vector space, in which similarity is measured by a fixed function; in our experiments, embeddings are L2-normalized and compared by Euclidean distance, which ranks items exactly as cosine similarity does. Each model induces its own embedding space and hence its own nearest neighbors, so everything below is defined for a single model, which we leave implicit. A query 𝑞 is an image or a text, embedded by the same model as the corpus. Searching a corpus of one modality with a query of one modality gives four query directions: image-to-image (i→i), textto-text (t→t), image-to-text (i→t), and text-to-image (t→i). The first two are uni-modal, the last two cross-modal. The distinction matters because an approximate index is built over the distribution of the corpus vectors. Uni-modal queries come from roughly that distribution; cross-modal queries often do not, because contrastively trained models place the two modalities in partly separated regions of the embedding space [29], so a query of one modality may lie far from the items of the other [7]. The extent of this separation varies across models. We call a pair of model and query direction a setting.

2.2

Index Families and Configurations

Approximate nearest-neighbor (ANN) indexes avoid comparing a query with every item, at the price of sometimes missing true neighbors. We consider three widely deployed index families, which approximate search in different ways and therefore lose accuracy for different reasons. HNSW. HNSW [32] builds a multi-layer proximity graph over the corpus vectors and answers a query by greedy best-first traversal, keeping a candidate list of size efSearch. Its build-time parameters are the graph degree 𝑀 and efConstruction. HNSW keeps full-precision vectors, so its losses come from navigation: the traversal can stop in a region that does not contain all true neighbors, particularly for queries far from the data the graph was built on [7, 45]. IVFPQ. IVFPQ [9, 17] partitions the corpus around 𝑛 list centroids and compresses each vector with product quantization into a short code. A query probes the nprobe partitions whose centroids are closest to it and ranks their contents by approximate distance. It loses accuracy in two ways: true neighbors may lie in partitions that are not probed, and quantization may misorder those that are. O-IVFPQ. O-IVFPQ applies a learned rotation (OPQ [11]) before product quantization, which reduces quantization error for a given code length; otherwise it behaves like IVFPQ.

Configurations, catalog, and cost. A configuration 𝐴 is an index family together with values for its build-time and search-time parameters. A catalog A = {𝐴1, . . . , 𝐴𝑚 } is the set of configurations available for a corpus and model. Configurations that differ only in search-time parameters share one built index; all others need separate indexes. Each configuration has a per-query cost 𝑐 (𝐴), such as its mean search latency on a given platform. Cost depends on the model, for instance through the embedding dimension, so the cost order of a catalog can differ between models. Memory is a per-index cost and is reported separately.

2.3

Fidelity

Let Top-𝑘 KNN (𝑞) be the 𝑘 items of 𝐶 nearest to 𝑞, computed by exact search, and Top-𝑘𝐴 (𝑞) the 𝑘 items returned by configuration 𝐴. The fidelity of 𝐴 on 𝑞 is Top-𝑘 KNN (𝑞) ∩ Top-𝑘𝐴 (𝑞) ∈ [0, 1]. 𝑘 Fidelity is what the ANN literature calls recall@𝑘 against exact search; we use a separate name to distinguish it from recall against human relevance judgments. It isolates the loss caused by approximation: the model determines which items are nearest, and fidelity measures how many of them a configuration recovers. Computing it requires the exact top-𝑘, which is affordable offline for a sample of queries but is exactly what approximate indexes avoid at query time. A configuration is dominated if another configuration is no more expensive and has at least its mean fidelity, with one of the two strictly better, for the same model and query direction. A dominated configuration is never the better choice for the workload as a whole, but it can still be the cheapest configuration that meets a target on individual queries. F(𝑞, 𝐴) =

2.4

Problem: Per-Query Plan Selection

An operator fixes a fidelity target 𝜏 ∈ (0, 1] and a reliability level 𝜌 ∈ (0, 1]: a query should receive at least a fraction 𝜏 of its exact top-𝑘, and at most a fraction 1 − 𝜌 of the workload may fall short. We call the latter the requirement. For a query 𝑞, the sufficient configurations are those that meet the target, 𝑆𝜏 (𝑞) = { 𝐴 ∈ A : F(𝑞, 𝐴) ≥ 𝜏 }. Static plan. A static deployment runs every query of a workload 𝑊 on one configuration. The static plan is the cheapest configuration that meets the requirement on 𝑊 , |{𝑞 ∈ 𝑊 : 𝐴 ∈ 𝑆𝜏 (𝑞)}| ≥ 𝜌, |𝑊 | or, if no configuration meets it, the one that meets the target on the largest fraction of 𝑊 . Because a catalog offers only a few configurations, the static plan usually exceeds the requirement: it meets the target on more than a fraction 𝜌 of queries, because the next cheaper configuration meets it on fewer. 𝐴static = arg min 𝑐 (𝐴) 𝐴∈ A

s.t.

Per-query optimum. If every query’s fidelity under every configuration were known in advance, each query could run on its cheapest sufficient configuration, 𝐴∗ (𝑞) = arg min 𝑐 (𝐴). 𝐴∈𝑆𝜏 (𝑞)

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

Meaning corpus; embedding model catalog of configurations per-query cost of configuration 𝐴 result depth fidelity of 𝐴 on 𝑞 fidelity target; reliability level configurations sufficient for 𝑞 workload static plan; per-query optimum selected configuration per-query cost of selecting it landmarks; their number 𝑞 ’s nearest landmark (its cell) construction sample; held-out workload mean fidelity and coverage of 𝐴 𝑗 in cell 𝑖 estimated fidelity; estimated coverage price of an expected miss (budget rule)

Table 2: Notation.

This per-query optimum is not deployable, since it requires every query’s exact top-𝑘, but its cost bounds what any per-query choice can save. Section 4.5 defines the variants we compare against. ˆ Selection. A deployable selector chooses a configuration 𝐴(𝑞) for each query from estimates that are available before any configuration runs and that cost 𝑐 est per query to obtain. A violation ˆ occurs when 𝐴(𝑞) ∉ 𝑆𝜏 (𝑞), that is, when the chosen configuration misses the target. The goal is the selector with the lowest mean ˆ cost 𝑐 est + 𝑐 (𝐴(𝑞)) whose violation rate meets the requirement, at most 1 − 𝜌: the same requirement the static plan is built to meet. As a more conservative comparison, we also hold the selector to the violation rate the static plan actually incurs, which is usually lower. The two goals trade off: a selector that always picks the cheapest configuration minimizes cost but violates often, while the static plan meets the requirement at the cost of serving every query as if it were among the hardest.

hnsw_low

1.0 0.8 0.6 0.4 0.2 0.0

Figure 2: The offline stage on real data (Jina-v4, text-to-image, 𝐾 = 10,000): 40 neighboring image landmarks (crosses), projected to two dimensions, with each cell shaded by the mean fidelity of hnsw_low (left) and ivfpq_low (right) on the construction sample; grey: sparse cells. The cells are the same in both panels, but the fidelity in them is not.

Two properties make this more than a density estimate. First, the statistics are measured, not modeled: they capture whatever combination of density, partitioning, and graph structure determines fidelity in a region, without our having to know which. Second, they are kept separately for every configuration, because the same region can be easy for one index family and hard for another: a dense region whose neighbors straddle partition boundaries can be hard for IVFPQ and easy for HNSW, and a sparse region far from most data can be the reverse. The approach rests on two premises, which Sections 5.2 and 5.3 test directly: • Smoothness: fidelity varies slowly enough across the space that the sample queries in a region represent the queries that will fall into it later. This is least plausible near the boundary between regions and for queries far from all data, such as cross-modal queries under models that separate the modalities strongly. • Configuration specificity: the same region can have very different fidelity under different configurations, so statistics must be kept per pair of region and configuration.

3 THE FIDELITY SYNOPSIS 3.1 Overview and Intuition The fidelity of a configuration on a query is determined by the geometry of the corpus around the query: how densely its true neighbors are packed, how far they lie from it, whether they fall within one IVF partition or straddle several, and how well connected the part of the HNSW graph that contains them is. Two queries that land close to each other in the embedding space largely share these surroundings, and often many of their true neighbors, so we expect them to fare similarly under a given configuration. This suggests estimating fidelity by location. We divide the embedding space into regions and record, for each region and each configuration, how that configuration performed on a sample of queries that fell into the region; a new query is located and the record of its region is read off. This is the idea of a histogram in a relational optimizer, which records statistics per bucket of a column’s domain so that the selectivity of a new predicate can be read off without scanning the table. Here the buckets are regions of the embedding space, and the statistic is fidelity.

ivfpq_low cell mean fidelity on Q

Symbol

𝐶, 𝑀 A = {𝐴1 , . . . , 𝐴𝑚 } 𝑐 (𝐴) 𝑘 F(𝑞, 𝐴) 𝜏, 𝜌 𝑆𝜏 (𝑞) 𝑊 𝐴static , 𝐴∗ (𝑞) ˆ 𝐴(𝑞) 𝑐 est 𝐿, 𝐾 ℓ (𝑞) 𝑄 , 𝑄 test 𝜇𝑖 𝑗 , 𝜋𝑖 𝑗 (𝜏 ) 𝐹ˆ , 𝜋ˆ 𝜆

The synopsis is built once per model in an offline stage and consulted once per query in an online stage (Figure 1). Only the offline stage uses exact search, and only on a sample of queries.

3.2

Offline Stage: Building the Synopsis

The offline stage takes a model’s corpus embeddings, its catalog A = {𝐴1, . . . , 𝐴𝑚 }, and a construction sample 𝑄 (a set of queries for which exact search is affordable), and builds the synopsis in four steps. Figure 2 shows the result on real data. Step 1: Landmarks. We choose 𝐾 ≪ |𝐶 | landmarks 𝐿 = {ℓ1, . . . , ℓ𝐾 }, points in the embedding space obtained by spherical 𝑘-means on the corpus vectors. Each landmark defines a cell, the set of points closer to it than to any other landmark: 𝑉𝑖 = { 𝑥 : dist(𝑥, ℓ𝑖 ) ≤ dist(𝑥, ℓ𝑖 ′ ) for all 𝑖 ′ }.

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

The cells partition the space, so every query belongs to exactly one cell (ties are broken arbitrarily); they play the role of histogram buckets. Clustering places more landmarks, and hence smaller cells, where the corpus is dense. Each model has one landmark set per modality, and a query is located among the landmarks of the modality it searches: in text-to-image search, a text query is located among image landmarks. All configurations share the same landmarks, so the cells are the same for every configuration and only the statistics differ. Step 2: Fidelity labels. For every query 𝑞 ∈ 𝑄, we compute its exact top-𝑘 once, run every configuration 𝐴 𝑗 on it, and record 𝑦𝑞 𝑗 = F(𝑞, 𝐴 𝑗 ). This gives a |𝑄 | × 𝑚 table of true fidelities. It is the only step that uses exact search, once per sample query, since all configurations are compared against the same exact top-𝑘. Step 3: Assignment. Each sample query is assigned to the cell of its nearest landmark, ℓ (𝑞) = arg min dist(𝑞, ℓ𝑖 ),

𝑄𝑖 = { 𝑞 ∈ 𝑄 : ℓ (𝑞) = 𝑖 },

𝑖

and 𝑛𝑖 = |𝑄𝑖 | is the number of sample queries in cell 𝑖. Step 4: Aggregation. For each cell 𝑖 and configuration 𝐴 𝑗 , we keep the mean fidelity of the cell’s sample queries, 1 ∑︁ 𝜇𝑖 𝑗 = 𝑦𝑞 𝑗 , 𝑛𝑖 𝑞 ∈𝑄 𝑖

and a histogram of their fidelities over 𝐵 bins, from which we read, for any target 𝜏, the fraction of the cell’s queries on which 𝐴 𝑗 met it: 1 𝜋𝑖 𝑗 (𝜏) = { 𝑞 ∈ 𝑄𝑖 : 𝑦𝑞 𝑗 ≥ 𝜏 } . 𝑛𝑖 We call 𝜋𝑖 𝑗 (𝜏) the coverage of 𝐴 𝑗 in cell 𝑖: the estimated probability that 𝐴 𝑗 suffices for a query in this region. The mean says how good a configuration is on average; the coverage says how often it is good enough, which is what selection needs. Two cells with the same mean can differ sharply in coverage, if fidelity is uniformly moderate in one and high for most queries but very low for a few in the other. We use 𝐵 = 20 bins of width 0.05; for a target at a bin edge, such as 0.7, 0.8, or 0.9, the coverage read from the histogram is exact, and for a target inside a bin, the bin’s count is divided evenly among the fidelity values it holds. Sparse cells. A cell with few or no sample queries has unreliable or undefined statistics. If fewer than 𝑞 min sample queries fall into cell 𝑖, its statistics are replaced by those of the whole sample, 𝜇¯ 𝑗 and 𝜋¯ 𝑗 (𝜏). We use 𝑞 min = 10. Output. The synopsis consists of the 𝐾 landmarks, the count 𝑛𝑖 of each cell, and, for each cell and configuration, the mean 𝜇𝑖 𝑗 and a 𝐵-bin histogram: a 𝐾 × 𝑚 table with one row per cell and one column per configuration. Its size is 𝑂 (𝐾 (𝑑 + 𝑚𝐵)) numbers for 𝑑dimensional embeddings, dominated by the landmarks themselves, and it grows neither with the corpus nor with the sample. The label table of Step 2 is needed only to build the synopsis.

3.3

Online Stage: Selecting a Configuration

At query time, the synopsis chooses a configuration for a new query 𝑞 under the operator’s target 𝜏 and reliability level 𝜌. Because

each cell stores a histogram rather than a single number, the same synopsis serves any target. Step 1: Locate the query. We find the query’s nearest landmark, 𝑖 = ℓ (𝑞), by comparing 𝑞 with all 𝐾 landmarks, at a cost of 𝑂 (𝐾𝑑). Step 2: Read the estimates. Row 𝑖 of the synopsis gives, for every configuration at once, an estimated fidelity and an estimated coverage: 𝐹ˆ (𝑞, 𝐴 𝑗 ) = 𝜇𝑖 𝑗 ,

𝜋ˆ (𝑞, 𝐴 𝑗 ; 𝜏) = 𝜋𝑖 𝑗 (𝜏),

𝑗 = 1, . . . , 𝑚,

with the whole-sample statistics in place of 𝜇𝑖 𝑗 and 𝜋𝑖 𝑗 (𝜏) if the cell is sparse. No configuration has been run on 𝑞 at this point. Step 3: Select. The budget rule prices each configuration by its cost plus a charge for its estimated chance of missing the target,
ˆ 𝐴(𝑞) = arg min 𝑐 (𝐴 𝑗 ) + 𝜆 1 − 𝜋ˆ (𝑞, 𝐴 𝑗 ; 𝜏) . 𝐴𝑗 ∈ A

The single parameter 𝜆 is the price of an expected miss. A small 𝜆 favors cheap configurations and lets violations rise; a large one favors reliable configurations. We set 𝜆 once per target, offline, to the smallest value whose violation rate on the construction sample meets the requirement, at most 1 − 𝜌 (Section 4.5). Since the estimates depend only on the cell, the rule’s choice is fixed per cell and can be precomputed, so Step 3 reduces to a table lookup. The rule generalizes the static plan. With a single landmark (𝐾 = 1), every query falls into the same cell and receives the same configuration: the cheapest one whose violation rate on the sample meets the requirement, which is the static plan. With more landmarks, the choice varies across cells: cells where cheap configurations suffice are served cheaply, and cells where they do not are served by costlier ones. The saving over the static plan comes entirely from this variation. Simpler rules. Section 5.4 compares the budget rule with two simpler ones. The mean rule picks the cheapest configuration whose estimated fidelity 𝐹ˆ reaches 𝜏, and the one with the highest estimate if none does; it ignores how fidelity is spread within a cell. The coverage rule picks the cheapest configuration whose estimated coverage 𝜋ˆ reaches 𝜌 in the query’s cell, and the one with the highest coverage if none does; it enforces the requirement in every cell rather than over the workload, which is stricter and therefore costlier. ˆ Step 4: Execute. We run 𝐴(𝑞) and return its top-𝑘 result. The per-query overhead is one nearest-landmark search and one table lookup, independent of the corpus size, with no exact search.

4 EVALUATION SETUP 4.1 Benchmark We use image–caption pairs from LAION [39]. Of the 6,999,488 pairs available to us, we remove 307 with a degenerate side (267 images with a side shorter than 16 pixels, mostly thin strips and banners, and 40 captions that are missing, unreadable, or one to two characters long), and then 172,894 duplicates found by grouping near-identical SigLIP2 embeddings: 147,566 pairs whose image belongs to a large group of identical images under mostly unrelated captions, which we take to be a placeholder for an image that failed

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

Model

Checkpoint

Type

SigLIP2 OpenCLIP Jina-v4 Qwen3-VL

google/siglip2-so400m-patch16-512 ViT-L-14, laion2b_s32b_b82k jinaai/jina-embeddings-v4 Qwen/Qwen3-VL-Embedding-2B

dual encoder 1,152 dual encoder 768 VLM (Qwen2.5-VL) 2,048 VLM (Qwen3-VL) 2,048

𝑑 Tokens Precision 64 77 512 512

fp16 fp16 bf16 bf16

Table 3: Embedding models. 𝑑: embedding dimension; Tokens: maximum caption length; Precision: inference precision.

to download, and 25,328 extra copies of pairs whose image and caption both repeat, at least one of them in a large group; of each such pair we keep one copy. Duplicates make a query’s exact top-100 arbitrary, since tied items can be returned in any order; we remove the large groups (the largest 5% by size: eight or more identical images, or six or more identical captions), while smaller groups of repeated captions remain, so some queries still have ties at rank 100. The remaining 6,826,287 pairs are split once into three disjoint sets in proportions 85/10/5%, stratified on the 616 non-empty combinations of two 𝑘-means clusterings with 25 clusters each, one of the image and one of the caption embeddings (seed 0): • the corpus 𝐶 (5,802,772 pairs), which is indexed; • the construction sample 𝑄 (682,444 pairs), used only offline, to build the synopses, choose the static plan, and tune 𝜆; • the held-out workload 𝑄 test (341,071 pairs), on which all results are reported. The image and the caption of a pair always belong to the same set, so no query shares a pair with an item it searches. The split is computed in SigLIP2’s embedding space and reused for the other models, so that all models are evaluated on the same pairs. Each model indexes the images and the captions of 𝐶 as two separate collections, and every pair in 𝑄 and 𝑄 test provides an image query and a text query, each searched against both collections. This gives the four query directions, with 341,071 held-out queries per setting. Unless stated otherwise, 𝑘 = 100.

4.2

Embedding Models

We use four open-weight embedding models (Table 3), chosen to differ in properties that affect approximate search: their architecture (SigLIP2 [42] and OpenCLIP [10] are contrastively trained dual encoders, Jina-v4 [13] and Qwen3-VL [28] embedders built on vision–language models), their dimension, which affects the cost of every configuration and of the synopsis lookup, and how strongly they separate the two modalities, which determines how far cross-modal queries lie from the corpus they search [29]. Every structure (indexes, exact neighbors, landmarks, synopses) is built separately for each model; using four models tests whether our conclusions hold across independently built embedding spaces.

4.3

Configuration Catalog

For each model, we build three configurations of each index family, low, moderate, and high, giving nine configurations (Table 4), with FAISS [19] 1.15.1 (official cuVS build, with AVX2). The three tiers of a family differ in their build: HNSW in graph degree and efConstruction, the IVF families in code length. They were chosen by a parameter sweep on a 50,000-vector sample to reach mean fidelity bands of 0.65–0.75 (low), 0.75–0.85 (moderate), and at least 0.85 (high), averaged over the two directions an index serves; the

search parameter was then set per model at full scale, on 5,000 construction queries. At full scale every IVF-family tier lies in its band, but hnsw_low lies below its band for every model. Three tiers per family give a choice between cheap and expensive configurations both within and across families, while keeping the catalog small enough to run every configuration on every construction query. Reaching the bands requires nprobe values of 2,048–4,096 for SigLIP2 and OpenCLIP but only 16–256 for Jina-v4 and Qwen3VL. For SigLIP2 and OpenCLIP, every IVF-family configuration is therefore several times as expensive as hnsw_low, and most of them are dominated; for Jina-v4 and Qwen3-VL, the low and moderate IVF tiers cost between hnsw_low and hnsw_mod. No configuration is removed, since a dominated configuration can still be the cheapest sufficient one for individual queries. Table 5 gives the cost and mean fidelity of every configuration in every setting.

4.4

Cost Measurement

All costs are measured on dedicated nodes with an AMD EPYC 7763 processor (128 logical CPUs, 64 used) and 1 TB of RAM, with all indexes in memory; exact search and 𝑘-means run on NVIDIA A100-SXM4-80GB GPUs. We measure two regimes: single query, one query at a time on one thread, and batched, batches of 4,096 queries on 64 threads. Every measurement uses the same 5,000 queries drawn at random from 𝑄 test , after an untimed warm-up of 500 queries. In the batched regime, passes over the sample are repeated until at least 20 s and three passes have been timed, and we report the median pass; in the single-query regime, we report the mean and the 99th percentile. The cost 𝑐 (𝐴) of a configuration is its mean per-query latency for the given model and direction. The lookup cost 𝑐 est is timed with the same harness, queries, batch size, and number of threads, in a separate run on the same type of node. All headline results use the batched regime.

4.5

Synopsis Parameters and Reference Points

Synopsis parameters. Unless stated otherwise, each modality has 𝐾 = 10,000 landmarks; RQ5 varies 𝐾. Histograms have 𝐵 = 20 bins, and 𝑞 min = 10. We evaluate fidelity targets 𝜏 ∈ {0.7, 0.8, 0.9}, with 𝜏 = 0.7 as the default, and a reliability level of 𝜌 = 0.9, so the requirement allows at most 10% of queries to miss the target. Tuning 𝜆. The budget rule’s 𝜆 is chosen on 𝑄 by 5-fold crossfitting: the synopsis is built on four folds and its violation rate measured on the fifth, and we take the smallest 𝜆 whose out-of-fold violation rate meets the chosen limit; the final synopsis is then built on all of 𝑄. We use two limits: the requirement, at most 1 − 𝜌 (budget rule at the requirement, our method), and the violation rate of the static plan on 𝑄 (budget rule at the static rate, the conservative comparison of Section 2.4). If no 𝜆 reaches the limit, we use the one with the fewest violations. Reference points. We compare the synopsis with location-blind estimates (the global average fidelity and the global coverage of each configuration on 𝑄, which equal a synopsis with 𝐾 = 1), with a density-only estimate (RQ2), with a shared synopsis that keeps one difficulty value per cell for all configurations (RQ3), with the static plan, and with three versions of the per-query optimum. The matched optimum serves the same queries as the static plan

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

Configuration

Build parameters

Search parameter

Shared

Memory (GB)

hnsw_low hnsw_mod hnsw_high

𝑀=4, efC=40 𝑀=8, efC=80 𝑀=16, efC=40

efSearch=1024/1024/192/128 efSearch=1536/1024/192/256 efSearch=6144/6144/512/1024

no no no

54.1/36.3/95.7/95.7 54.5/36.7/96.1/96.1 55.2/37.4/96.8/96.8

ivfpq_low ivfpq_mod ivfpq_high

𝑛 list =32768, PQ288/192/512/512 𝑛 list =32768, PQ384/256/1024/1024 𝑛 list =32768, PQ1152/768/2048/2048

nprobe=2048/2048/16/16 nprobe=2048/2048/32/32 nprobe=4096/4096/128/256

no no no

3.7/2.5/6.6/6.6 4.9/3.3/12.5/12.5 13.8/9.2/24.4/24.4

oivfpq_low oivfpq_mod oivfpq_high

OPQ288/192/512/512, 𝑛 list =32768, PQ288/192/512/512 OPQ384/256/1024/1024, 𝑛 list =32768, PQ384/256/1024/1024 OPQ1152/768/2048/2048, 𝑛 list =32768, PQ1152/768/2048/2048

nprobe=2048/2048/16/16 nprobe=2048/2048/32/32 nprobe=4096/4096/128/256

no no no

3.8/2.5/6.6/6.6 4.9/3.3/12.6/12.6 13.8/9.2/24.4/24.4

Table 4: The nine configurations of the catalog, with per-model values in the order SigLIP2/OpenCLIP/Jina-v4/Qwen3-VL. Every configuration is a separate build; memory is that of the image and the text index together. Table 5 gives each configuration’s cost and mean fidelity per setting.

and possibly more: it runs every query whose cheapest sufficient configuration costs no more than the static plan, and charges every other query the static plan’s cost. The optimum at the requirement is the cheapest assignment of configurations that misses at most 1 − 𝜌 of the queries; no selector that meets the requirement can be cheaper. The unconstrained optimum serves every query that some configuration can serve. Table 6 defines each precisely.

which is 0 for no improvement over the static plan and 1 for a selector as cheap as the corresponding optimum, and is reported only where that optimum is at least 5% cheaper than the static plan. A selector can exceed 1 only by violating more often than the optimum allows; in our results, only selectors that violate more often than the static plan do.

4.6

4.7

Metrics

All metrics are computed on 𝑄 test , for synopses, static plans, and 𝜆 fitted on 𝑄. Estimation metrics are computed per configuration and averaged over configurations, excluding flat configurations, whose true fidelity has a standard deviation below 0.03 in a direction, since skill is not meaningful on a near-constant target. Table 6 summarizes all metrics and the abbreviations used in the tables; we define the main ones here. Accuracy of estimates. For the estimated fidelity, we report the mean absolute error and the MSE skill score [33], Skill = 1 −

MSE( 𝐹ˆ) , MSE(global average)

which is 0 for an estimate no better than the global average, 1 for a perfect one, and negative for a worse one. For the estimated coverage, a predicted probability of the event F(𝑞, 𝐴 𝑗 ) ≥ 𝜏, we report the Brier skill score [12], the same construction applied to the mean squared error of that probability against the global coverage; the AUC for separating queries that meet the target from those that do not; and the expected calibration error (ECE) [14, 34], over 10 ˆ restricted to pairs of query and configuration equal-width bins of 𝜋, with 0.05 < 𝜋ˆ < 0.95, since ECE over all pairs is dominated by configurations whose coverage is trivially 0 or 1. Plan selection. For a selector, we report its relative cost, the mean ˆ of 𝑐 est + 𝑐 (𝐴(𝑞)) divided by the cost of the static plan; its violation rate; and the share of the available saving it captures, the savings recovered, 𝑐 (𝐴static ) − 𝑐¯selector , 𝑐 (𝐴static ) − 𝑐¯opt

Statistical Analysis

With 341,071 held-out queries per setting, almost any difference is statistically significant, so we lead with effect sizes and confidence intervals and use hypothesis tests as supporting evidence. We compute 95% bootstrap confidence intervals with 1,000 resamples; since queries in the same cell share their estimate, we resample cells rather than individual queries. Each comparison uses a paired test suited to its outcome: the Wilcoxon signed-rank test on perquery squared error for estimation error (synopsis against global average in RQ2, keyed against shared synopsis in RQ3), the same test with Pratt’s handling of zero differences for shortfall (RQ4), and McNemar’s test on per-query outcomes for violations (RQ4). Within each family of tests, 𝑝-values are corrected across settings with the Benjamini–Hochberg procedure at a false discovery rate of 𝑞 < 0.05.

Robustness. Over three seeds of the landmark clustering, at 𝐾 = 10,000 and 𝜏 = 0.7, the standard deviation of skill, Brier skill, relative cost, and violation rate is small in every setting (at most 0.008 for skill and 0.010 for Brier skill, 0.03 for relative cost, and a quarter of a percentage point for violation rates), so no conclusion depends on the seed.

5

EXPERIMENTS

We answer five research questions. RQ1 measures the opportunity; RQ2 and RQ3 test the synopsis’s two premises; RQ4 evaluates plan selection end to end; RQ5 measures the cost of the synopsis and its sensitivity to its parameters.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

SigLIP2

OpenCLIP

Jina-v4

Dir. Configuration

Cost

i→i hnsw_low hnsw_mod hnsw_high ivfpq_low ivfpq_mod ivfpq_high oivfpq_low oivfpq_mod oivfpq_high

651 1,609 13,439 3,582 18,365 23,743 3,455 18,251 23,468

0.683 0.964 0.978 0.890 0.935 0.992 0.889 0.935 0.993

484 878 8,796 3,050 12,263 14,833 2,341 12,194 14,818

0.674 208 0.728 160 0.656 0.950 451 0.936 527 0.949 0.973 1,141 0.978 1,976 0.981 0.874 297 0.817 313 0.815 0.923 420 0.899 399 0.895 0.989 1,855 0.969 3,549 0.976 0.874 323 0.819 353 0.816 0.924 428 0.899 407 0.895 0.991 2,023 0.969 3,842 0.977

i→t hnsw_low hnsw_mod hnsw_high ivfpq_low ivfpq_mod ivfpq_high oivfpq_low oivfpq_mod oivfpq_high

647 1,579 13,145 2,958 17,648 19,339 3,027 17,609 19,233

0.311 0.748 0.831 0.486 0.644 0.862 0.493 0.653 0.865

494 961 8,560 2,247 12,106 13,854 2,232 12,040 13,786

0.358 234 0.601 171 0.468 0.714 525 0.868 581 0.869 0.744 1,384 0.941 1,870 0.940 0.540 309 0.703 311 0.729 0.714 397 0.809 397 0.834 0.926 1,813 0.925 3,848 0.958 0.562 302 0.702 337 0.729 0.727 403 0.809 393 0.835 0.929 2,008 0.925 3,483 0.959

t→i hnsw_low hnsw_mod hnsw_high ivfpq_low ivfpq_mod ivfpq_high oivfpq_low oivfpq_mod oivfpq_high

673 1,735 13,150 3,116 17,755 20,083 2,991 17,693 19,983

0.490 0.871 0.933 0.468 0.626 0.876 0.477 0.634 0.878

531 923 8,646 2,018 11,725 12,335 1,972 11,741 12,133

0.525 228 0.562 146 0.386 0.860 506 0.823 532 0.733 0.939 1,130 0.915 2,071 0.897 0.493 320 0.670 337 0.530 0.645 384 0.782 384 0.648 0.899 1,703 0.907 3,369 0.871 0.512 302 0.672 322 0.531 0.654 418 0.782 395 0.648 0.901 1,857 0.907 3,780 0.871

t→t hnsw_low hnsw_mod hnsw_high ivfpq_low ivfpq_mod ivfpq_high oivfpq_low oivfpq_mod oivfpq_high

688 1,687 14,220 3,751 18,735 27,356 3,865 18,638 27,188

0.500 0.912 0.929 0.878 0.926 0.988 0.879 0.927 0.989

450 971 9,146 2,473 12,329 16,032 2,449 12,338 15,812

0.470 221 0.611 176 0.522 0.842 501 0.886 602 0.905 0.809 1,226 0.937 2,192 0.953 0.878 311 0.765 306 0.770 0.926 391 0.849 404 0.850 0.988 1,779 0.931 4,010 0.950 0.879 316 0.764 323 0.770 0.927 400 0.849 412 0.850 0.989 1,874 0.931 3,737 0.950

Cost

𝐹¯ Cost

Qwen3-VL

𝐹¯

𝐹¯ Cost

𝐹¯

Table 5: Per-query cost (𝜇s per query; controlled benchmark, batches of 4,096 on 64 threads) and mean fidelity 𝐹¯ on 𝑄 test of every configuration, per model and direction.

5.1

RQ1: How much can per-query plan selection save?

Before evaluating the synopsis, we measure the opportunity it targets: how much cheaper a workload would be if every query ran on its cheapest sufficient configuration. Table 7 reports, for each setting at 𝜏 = 0.7, the static plan, how the held-out queries are distributed by the cost of their cheapest sufficient configuration, and the cost of the per-query optimum. We use the matched optimum, which serves at least every query the static plan serves and is therefore the like-for-like comparison; the unconstrained optimum also pays for queries the static plan misses, and can cost more. The opportunity is large in most settings. At matched service, per-query selection would lower cost in every setting, and to about half of the static plan in a typical one. The settings fall into three

groups (bold and grey in Table 7). In seven cross-modal settings, the opportunity is large: the static plan is the most accurate tier of a family, yet most queries would meet the target on a configuration costing at most a third as much. In seven settings, the opportunity is moderate: most queries could use a cheaper configuration, mostly one costing between a third and the whole of the static plan. In two settings, it is small: the static plan is hnsw_mod, and its only cheaper alternative, hnsw_low, suffices for only part of the queries. The hardest queries set the price for all of them. The size of the opportunity follows from two quantities: how expensive the static plan is, and how many queries actually need it. The static plan must serve a fraction 𝜌 of the workload, so it is sized for the hardest queries within that fraction. Where these force hnsw_high, which costs several times as much as hnsw_mod, every query pays for

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

Term (abbreviation)

Meaning

Workload and baselines Setting Requirement Static plan Serves Cheapest sufficient configuration Optimum, matched Optimum, unconstrained (all) Optimum, ≤ 1−𝜌

A pair of embedding model and query direction; 16 in total. At most a fraction 1 − 𝜌 = 10% of queries may miss the fidelity target 𝜏 . The cheapest single configuration that meets 𝜏 on at least a fraction 𝜌 of 𝑄 ; if none does, the one that meets it most often (∗ , §). Share of held-out queries on which a configuration meets 𝜏 . The cheapest configuration that meets 𝜏 on a given query; buckets give its cost relative to the static plan (none: no configuration meets 𝜏 ). Runs every query whose cheapest sufficient configuration costs no more than the static plan on that configuration, and charges every other query the cost of the static plan; it serves at least every query that the static plan serves. Runs every query that some configuration can serve on its cheapest sufficient configuration, and every other query on its highest-fidelity configuration. The cheapest assignment of configurations that misses 𝜏 on at most 1 − 𝜌 of the held-out queries, a missed query running on the cheapest configuration; no selector that meets the requirement is cheaper (infeas.: more than 1 − 𝜌 of queries cannot be served by any configuration).

Selection rules (all use the synopsis’s estimates for the query’s cell) Mean rule The cheapest configuration whose estimated fidelity 𝐹ˆ reaches 𝜏 . Coverage rule The cheapest configuration whose estimated coverage 𝜋ˆ reaches 𝜌 ; if none does, the one with the highest coverage. Budget rule arg min 𝑗 𝑐 (𝐴 𝑗 ) + 𝜆 (1 − 𝜋ˆ 𝑗 ) , with 𝜆 tuned on 𝑄 to a violation limit: the requirement, 1 − 𝜌 (at the requirement, ≤ 1−𝜌 ; our method), or the static plan’s violation rate on 𝑄 (at the static rate, static viol.); ‡: limit not reachable, fewest violations used. Selection metrics (on 𝑄 test ) Cost Violation rate (Viol.) Shortfall (Short.) Savings recovered (Rec.)

†

ˆ Mean of 𝑐 est + 𝑐 (𝐴(𝑞) ) , relative to the static plan (1× ). Share of queries whose chosen configuration misses 𝜏 . ˆ Mean of 𝜏 − F(𝑞, 𝐴(𝑞) ) over violated queries. Share of the optimum’s saving over the static plan that a selector captures: against the matched optimum, except for the budget rule at the requirement, measured against the optimum at ≤ 1−𝜌 ; shown where that optimum saves at least 5%. The coverage rule’s violated queries fall less far below 𝜏 than the mean rule’s (mean shortfall over violated queries).

Estimation metrics (on 𝑄 test , averaged over non-flat configurations) Non-flat configuration True fidelity has a standard deviation of at least 0.03 in the direction. Global average (GA), global cover- Location-blind estimates: a configuration’s mean fidelity, or share of queries meeting 𝜏 , on all of 𝑄 ; equivalent to a synopsis with 𝐾 = 1. age Density-only (DO) Global average plus a linear term in the local density of the query’s cell (mean distance from its landmark to its 100 nearest corpus vectors), with one slope per configuration (per-cfg) or one for all (shared). Skill MSE skill score of the estimated fidelity against the global average: 0 no better, 1 perfect. 𝜌𝑠 Spearman rank correlation between estimated and true fidelity. Share of fidelity variance that lies between cells on 𝑄 test ; approximately the highest skill any estimate with one value per cell can reach. ICC Interior (Int.), boundary (Bnd.) Skill on the third of queries with the lowest, or highest, ratio of distances to the nearest and second-nearest landmark. Brier skill (BSS) Skill of the estimated coverage, as a probability of meeting 𝜏 , against the global coverage. AUC, ECE How well the estimated coverage separates queries that meet 𝜏 from those that do not; its expected calibration error over 10 bins, for 0.05 < 𝜋ˆ < 0.95. Keyed, shared synopsis The synopsis, with statistics per configuration; a variant with one difficulty offset per cell for all configurations. Thin Share of held-out queries in cells with fewer than 𝑞 min sample queries. Configuration abbreviations H, I, O; l, m, h

HNSW, IVFPQ, O-IVFPQ; low, moderate, high tier. In the single index, l, m, h are its three efSearch settings, and in the union, S-l and S-m are its two lower ones.

Table 6: Ready reckoner: the terms, metrics, and abbreviations used in the tables of Section 5.

them, although in the large-opportunity settings fewer than a fifth of queries need the static plan’s configuration. Conversely, where most queries do need it, as in SigLIP2 t→t, the opportunity is small. Every setting with a hard tail of this kind is cross-modal, consistent with cross-modal queries lying away from the corpus distribution; the only cross-modal setting without one is Qwen3-VL i→t.

Which configurations provide the saving. Figure 3 breaks the heldout queries down by their cheapest sufficient configuration. For SigLIP2 and OpenCLIP, it is usually an HNSW configuration: their IVF-family configurations probe thousands of partitions and are the cheapest choice mainly where HNSW falls short, as in image-to-text search. For Jina-v4 and Qwen3-VL, whose low and moderate IVF tiers are cheaper than hnsw_mod, an IVF-family configuration is the cheapest sufficient one for a quarter to two thirds of the queries.

Since every configuration in this catalog is a separate index, capturing the saving requires keeping several indexes built; Section 5.4.1 examines how much of it a smaller catalog retains. Reliability as well as cost. Per-query selection can also serve queries that the static plan misses: up to a tenth of queries (column “> 1×”) miss the target under the static plan but meet it under a costlier configuration. The share is largest for Jina-v4 and Qwen3VL i→i, whose static plan only just meets the requirement. Queries that no configuration can serve are rare, at most 5% in any setting. The static plan generalizes. The static plan, chosen on 𝑄, meets the target on at least 90% of the held-out queries in every setting where some configuration meets it on 90% of 𝑄. The baseline is therefore stable across samples, and the opportunity is not an artifact of evaluating a plan on the queries it was tuned on.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

Static

Queries whose cheapest sufficient plan costs

Optimum cost

Model

Dir.

Static plan

serves

≤ 0.33×

1×

> 1×

none

all

matched

SigLIP2

i→i i→t t→i t→t

hnsw_mod oivfpq_high∗ hnsw_high hnsw_mod

99.2% 89.9% 97.4% 96.6%

0.0% 68.1% 89.7% 0.0%

53.8% 45.3% 21.6% 6.8% 0.0% 7.7% 21.2% 75.4%

0.8% 0.1% 1.6% 3.1%

0.0% 0.72× 3.4% 0.30× 1.0% 0.21× 0.2% 0.94×

0.68× 0.31× 0.20× 0.87×

OpenCLIP

i→i i→t t→i t→t

hnsw_mod oivfpq_high hnsw_high oivfpq_low

97.5% 97.2% 98.4% 99.1%

0.0% 64.7% 88.8% 19.3%

55.5% 42.0% 22.7% 10.5% 0.0% 9.6% 69.0% 11.2%

2.5% 0.1% 1.5% 0.3%

0.0% 0.92× 2.1% 0.33× 0.1% 0.20× 0.2% 0.44×

0.75× 0.33× 0.20× 0.43×

Jina-v4

i→i i→t t→i t→t

ivfpq_mod hnsw_high hnsw_high hnsw_mod

90.9% 97.2% 93.7% 91.6%

0.0% 79.0% 58.3% 0.0%

82.4% 12.0% 25.7% 85.7%

8.6% 6.7% 10.1% 8.3%

8.7% 0.9% 1.2% 4.4%

0.2% 0.68× 1.4% 0.30× 4.7% 0.41× 1.6% 0.71×

0.62× 0.30× 0.39× 0.61×

Qwen3-VL

i→i i→t t→i t→t

ivfpq_mod hnsw_mod hnsw_high hnsw_mod

90.1% 90.6% 92.6% 93.6%

0.0% 16.5% 76.8% 28.6%

81.6% 67.1% 0.0% 56.2%

8.6% 9.1% 18.2% 10.1%

9.8% 6.9% 3.6% 4.4%

0.0% 0.73× 0.4% 0.79× 1.4% 0.39× 0.7% 0.67×

0.61× 0.60× 0.37× 0.54×

0.33–1×

Table 7: Opportunity for per-query selection at 𝜏 = 0.7: the static plan and the share of held-out queries it serves; the held-out queries by the cost of their cheapest sufficient configuration, relative to the static plan; and the mean cost of the unconstrained and the matched optimum. Bold: large opportunity (matched optimum below 0.4×); grey: small (above 0.7×). Terms: Table 6.

share of held-out queries (%)

SigLIP2

OpenCLIP

Jina-v4

Qwen3-VL

100 80 60 40 20 0 i→i hnsw low

i→t

t→i

hnsw mod

t→t hnsw high

i→i

i→t

ivfpq low

t→i

t→t

ivfpq mod

i→i

i→t

ivfpq high

t→i

t→t

oivfpq low

i→i

i→t

oivfpq mod

t→i

t→t

oivfpq high

none

Figure 3: Held-out queries by their cheapest sufficient configuration (𝜏 = 0.7); none: no configuration meets the target. Shades: low, moderate, and high tier of each family. Other targets. At 𝜏 = 0.8 and 0.9, the matched optimum is again at least 5% cheaper than the static plan in every setting, with a median close to half of it.

Answer to RQ1. At the same level of service, per-query configuration choice would roughly halve the cost of a static deployment in a typical setting, and save most where the static plan is sized for a small hard tail of cross-modal queries. Whether this opportunity can be captured without knowing each query’s fidelity in advance is the subject of RQ2–RQ4.

5.2

RQ2: Does a query’s location predict its fidelity?

The smoothness premise says that queries in the same cell have similar fidelity under a given configuration. The synopsis provides two estimates per configuration, the cell mean 𝐹ˆ and the coverage ˆ selection uses the coverage, while the mean is the most direct test 𝜋; of whether location carries information about fidelity at all. Table 8 evaluates both on every held-out query, against the location-blind global average and global coverage. Location carries information in every setting. The synopsis is more accurate than the global average in every setting, with skill well above zero everywhere (all confidence intervals exclude zero,

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

Model

Dir.

MAE GA Synopsis Skill [95% CI]

DO skill per-cfg shared

SigLIP2

i→i i→t t→i t→t

0.053 0.118 0.136 0.054

0.031 0.090 0.104 0.034

0.581 [0.574, 0.588] 0.349 [0.320, 0.378] 0.320 [0.310, 0.330] 0.587 [0.466, 0.663]

0.348 0.033 0.017 0.059

OpenCLIP i→i i→t t→i t→t

0.062 0.090 0.120 0.067

0.034 0.067 0.090 0.043

Jina-v4

i→i i→t t→i t→t

0.087 0.116 0.151 0.109

Qwen3-VL i→i i→t t→i t→t

0.085 0.102 0.189 0.106

Skill Coverage 𝜋ˆ , 𝜏=0.7 Int. Bnd. BSS [95% CI] AUC

𝜌𝑠

ICC

ECE

0.294 0.030 0.004 0.032

0.728 0.609 0.583 0.632

0.591 0.357 0.331 0.595

0.529 0.390 0.285 0.758

0.512 0.274 0.251 0.284

0.199 [0.181, 0.216] 0.219 [0.200, 0.237] 0.204 [0.196, 0.212] 0.493 [0.360, 0.574]

0.889 0.832 0.814 0.921

0.0028 0.0021 0.0018 0.0053

0.594 [0.587, 0.601] 0.386 [0.365, 0.407] 0.364 [0.330, 0.392] 0.578 [0.471, 0.641]

0.389 0.339 0.016 0.008 0.075 0.053 0.038 −0.029

0.734 0.599 0.592 0.597

0.604 0.398 0.374 0.584

0.516 0.374 0.382 0.730

0.529 0.329 0.310 0.261

0.237 [0.226, 0.250] 0.230 [0.218, 0.241] 0.214 [0.195, 0.229] 0.503 [0.377, 0.564]

0.907 0.840 0.830 0.924

0.0030 0.0025 0.0035 0.0027

0.052 0.078 0.098 0.073

0.527 [0.518, 0.535] 0.461 [0.440, 0.481] 0.475 [0.456, 0.494] 0.461 [0.445, 0.477]

0.342 0.204 0.300 0.221

0.275 0.196 0.293 0.218

0.725 0.692 0.702 0.700

0.535 0.489 0.486 0.470

0.281 0.413 0.438 0.500

0.458 0.380 0.375 0.336

0.273 [0.263, 0.281] 0.286 [0.264, 0.309] 0.331 [0.314, 0.349] 0.274 [0.261, 0.287]

0.897 0.866 0.867 0.865

0.0050 0.0049 0.0035 0.0045

0.054 0.076 0.146 0.069

0.481 [0.472, 0.490] 0.364 [0.339, 0.393] 0.317 [0.279, 0.351] 0.505 [0.481, 0.534]

0.296 0.104 0.109 0.157

0.145 0.072 0.083 0.146

0.693 0.621 0.565 0.708

0.491 0.393 0.325 0.513

0.235 0.295 0.278 0.564

0.408 0.270 0.238 0.377

0.233 [0.225, 0.240] 0.203 [0.181, 0.226] 0.236 [0.216, 0.253] 0.314 [0.289, 0.341]

0.858 0.832 0.812 0.880

0.0042 0.0056 0.0038 0.0034

Table 8: Accuracy of the synopsis’s two estimates on the held-out queries (𝐾 = 10,000), averaged over non-flat configurations: estimated fidelity against the global average (GA) and the density-only estimate (DO), and estimated coverage. ECE: pooled over the pairs of query and configuration of all nine configurations, as in Figure 4. Bold: the better-predicted of interior and boundary queries. Terms: Table 6.

and every per-configuration Wilcoxon test is significant). Location alone explains roughly half of the variance in fidelity in a typical setting, and the synopsis orders queries by fidelity moderately well. Local density does not explain it: the density-only estimate has much lower skill than the synopsis in every setting, so the synopsis captures more than how crowded a region is. The information is partial, however: the other half of the variance lies among queries within the same cell, where the synopsis cannot see it. Whether the synopsis nevertheless chooses configurations well is the question of RQ4. The synopsis reaches almost all that its partition allows. The ICC column, the share of fidelity variance that lies between cells on the held-out queries themselves, approximates the highest skill any estimate with one value per cell could reach. The synopsis’s skill, with cell means estimated on the construction sample, comes within a few hundredths of it in every setting. The cell statistics therefore carry over to new queries almost unchanged: the synopsis is limited not by its sample or by overfitting, but by how finely the space is partitioned and how much fidelity varies within a cell. Consistent with this, skill rises with the number of landmarks until cells become too thin (Section 5.5). The coverage estimate is calibrated. The coverage that selection relies on is also informative: its Brier skill is positive in every setting, and it separates queries that meet the target from those that do not well (AUC above 0.8 everywhere). It is also well calibrated (Figure 4): among queries for which the synopsis predicts a coverage of, say, 0.8, close to 80% meet the target. Calibration is what makes the reliability level meaningful: if the coverage is calibrated, a selector

that controls the expected number of misses controls the actual number. Location predicts better for uni-modal search. For SigLIP2, OpenCLIP, and Qwen3-VL, skill is higher for both uni-modal directions than for both cross-modal ones, as the smoothness premise predicts (for Jina-v4, cross-modal skill, 0.461 and 0.475, is as high as its text-to-text skill, 0.461): a cross-modal query is located among the landmarks of the other modality, which represent its surroundings less well. Measured by the mean distance from a query to its nearest landmark, cross-modal queries lie about twice as far as unimodal ones for SigLIP2, and less far for OpenCLIP, Qwen3-VL, and Jina-v4. Jina-v4, with the smallest gap, on average, has the highest cross-modal skill, but Qwen3-VL, with a smaller gap than SigLIP2 and OpenCLIP, has cross-modal skill as low as theirs, so the gap explains the difference only in part. Queries near cell boundaries. The premise is least plausible near the boundary between two cells. We compare interior queries, the third whose nearest landmark is much closer than the secondnearest, with boundary queries, the third for which the two are almost equally close (bold in Table 8: the better-predicted group). For text-to-text search, interior queries are predicted much better in all four models; for cross-modal search, better but by less. For image-to-image search, skill is higher for boundary queries under OpenCLIP, Jina-v4 and Qwen3-VL. This is an artifact of how skill is normalized: skill in each group is measured against that group’s own variance, and interior image queries vary much less. In absolute error, interior queries are predicted more accurately in all 16 settings, as the premise expects.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

SigLIP2 (ECE ≤ 0.0053)

SigLIP2

OpenCLIP (ECE ≤ 0.0035) 0.20

i→i i→t t→i t→t

map MAE

observed share F ≥ 0.7

1.0

0.5

OpenCLIP

t→i t→t

0.10 0.05

0.50

0.75

1.00

1.25

0.6

Jina-v4

0.0

Jina-v4 (ECE ≤ 0.0050)

0.8

1.0

1.2

Qwen3-VL

0.20

Qwen3-VL (ECE ≤ 0.0056) map MAE

1.0

observed share F ≥ 0.7

0.15

i→i i→t

0.15 0.10 0.05

0.5

0.4

0.6

0.8

0.6

0.8

1.0

distance to nearest landmark d1 (decile means) 0.0 0.0

0.5

1.0

0.0

map coverage π̂

0.5

1.0

map coverage π̂

Figure 4: Calibration of the estimated coverage (𝜏 = 0.7, 𝐾 = 10,000, nine configurations pooled): mean predicted coverage against the share of held-out (query, configuration) pairs that meet the target, in 10 bins over pairs with 0.05 < 𝜋ˆ < 0.95. Dashed: perfect calibration.

Model

HNSW Shared Keyed [CI of diff.]

SigLIP2 0.256 OpenCLIP 0.261 Jina-v4 0.252 Qwen3-VL −0.021

0.466 [0.205, 0.216] 0.516 [0.244, 0.268] 0.430 [0.173, 0.184] 0.312 [0.317, 0.352]

IVFPQ Shared Keyed [CI] 0.283 0.167 0.434 0.324

0.445 [0.128, 0.244] 0.451 [0.211, 0.471] 0.506 [0.070, 0.074] 0.469 [0.141, 0.149]

O-IVFPQ Shared Keyed [CI] 0.278 0.162 0.435 0.324

0.442 [0.129, 0.247] 0.450 [0.215, 0.474] 0.506 [0.069, 0.074] 0.469 [0.141, 0.150]

Table 9: Skill of the keyed synopsis (statistics per configuration, bold) and the shared synopsis (one offset per cell), per index family, averaged over directions and non-flat configurations (𝐾 = 10,000). Brackets: 95% confidence interval of the difference.

Figure 5 shows the same continuously: in every setting, the synopsis’s error is higher for the queries farthest from their nearest landmark than for the nearest ones. The cross-modal queries of SigLIP2 and OpenCLIP lie far from all landmarks, and their error is high throughout. Answer to RQ2. Yes. A query’s location predicts its fidelity in every setting, the synopsis captures almost all of the variation between cells available at its resolution, and its coverage estimate is well calibrated. Location is more informative for uni-modal than for cross-modal search, and less informative near cell boundaries, as the smoothness premise predicts.

Figure 5: Error of the estimated fidelity (mean absolute error over non-flat configurations) against the distance 𝑑 1 from a held-out query to its nearest landmark, in ten equal-count bins per direction (𝐾 = 10,000).

5.3

RQ3: Must the synopsis be kept per configuration?

The configuration-specificity premise says that the same region can be easy for one configuration and hard for another, so statistics must be kept for every pair of cell and configuration. We compare the synopsis with a shared variant that keeps one difficulty value per cell: the average, over configurations, of how far the cell’s mean fidelity lies from the configuration’s global mean. The shared synopsis knows which regions are harder or easier than average, but assumes they are equally so for every configuration. Table 9 reports both per index family. Keeping the synopsis per configuration is always better. The keyed synopsis has higher skill than the shared synopsis for every model and index family, with confidence intervals for the difference that exclude zero and every per-configuration test significant. The shared synopsis is not useless, since its skill is positive in all but one combination: some regions are harder than others for every configuration alike. But one value per cell captures only part of what the keyed synopsis captures. The gap follows the index families. The shared offset averages over all nine configurations, six of which are IVF-family, so it mostly describes how IVF-family configurations behave. For Jina-v4 and Qwen3-VL, the two synopses are therefore close for the IVF families but far apart for HNSW, whose pattern of easy and hard regions differs. For SigLIP2 and OpenCLIP, the gap is large for the IVF families as well: there, HNSW and IVF-family configurations agree much less on which regions are hard (Figure 6), so no single offset fits both. Configurations of the same family largely agree with each other. Giving each configuration its own scale on the shared offset

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search 1.0

OpenCLIP t→t

0.8

HNSW-m HNSW-h

0.6

PQ-l PQ-m PQ-h

0.4

OPQ-l OPQ-m

0.2 OPQ-h

OPQ-m

PQ-h

OPQ-l

PQ-l

PQ-m

HNSW-h

HNSW-l

HNSW-m

OPQ-h

OPQ-m

PQ-h

OPQ-l

PQ-l

PQ-m

HNSW-h

HNSW-l

HNSW-m

OPQ-h

Pearson r of cell means

Jina-v4 t→i HNSW-l

0.0

Figure 6: Correlation, across cells, of the mean fidelity of every pair of configurations (𝐾 = 10,000; l/m/h: low/moderate/high tier), in the setting where index families agree most (left, Jina-v4 t→i) and least (right, OpenCLIP t→t).

Model

Dir. Pair 𝐴 / 𝐵 (Similar cost)

𝐴 wins 𝐵 wins #pairs

SigLIP2

i→i i→t t→i t→t

hnsw_high / ivfpq_mod hnsw_high / oivfpq_high hnsw_high / oivfpq_high hnsw_high / oivfpq_mod

2.5% 3.7% 13.7% 0.0%

0.3% 17.6% 1.2% 4.9%

0 0 2 0

OpenCLIP i→i i→t t→i t→t

hnsw_high / ivfpq_mod hnsw_high / oivfpq_mod hnsw_high / oivfpq_high hnsw_high / oivfpq_high

1.3% 13.1% 9.0% 0.0%

0.2% 9.1% 2.0% 64.2%

0 2 4 0

i→i i→t t→i t→t

hnsw_high / oivfpq_high oivfpq_mod / hnsw_mod ivfpq_mod / hnsw_mod oivfpq_mod / hnsw_mod

0.3% 0.6% 0.7% 1.0%

0.2% 20.4% 15.7% 10.8%

0 0 0 0

Qwen3-VL i→i i→t t→i t→t

hnsw_high / ivfpq_high oivfpq_mod / hnsw_mod hnsw_high / oivfpq_high oivfpq_mod / hnsw_mod

0.1% 0.8% 16.3% 0.6%

0.3% 11.4% 12.4% 21.6%

0 0 4 0

Jina-v4

Table 10: Rank reversals between configurations of different families with similar cost (within 2×; 𝐴 the cheaper), over cells with at least 𝑞 min sample queries (𝐾 = 10,000). For each setting: the pair that reverses most often, the share of cells in which each wins by more than 0.1 in mean fidelity, and how many of the 36 pairs reverse in at least 5% of cells each way (bold: any).

narrows the gap but does not close it in any model or family: the regional pattern differs across configurations, not only its size. Configurations differ in how much fidelity they lose, not mainly in their order. One might expect configuration specificity to show up as reversals: regions where configuration 𝐴 beats 𝐵 and others where 𝐵 beats 𝐴. Table 10 shows that reversals are the exception: in most settings, no pair of the 36 formed by the nine configurations reverses in a substantial share of cells, and the pair that reverses most often is usually lopsided. Two-way reversals occur only in four cross-modal settings (bold). In a given region, configurations largely agree on which of them is better but differ in how much fidelity they lose, and the latter is what selection depends on: whether a

configuration meets the target in a region changes with the size of its loss even when the order of configurations does not. Answer to RQ3. Yes. A single difficulty value per cell carries some information, but keeping statistics per configuration improves skill for every model and index family, most where index families behave differently. Configurations largely agree on which of them is better in a region and disagree on how much fidelity the region costs them, which is what selection depends on. Keeping per-configuration statistics costs little: the synopsis is a small fraction of the size of a single index (Section 5.5).

5.4

RQ4: Does synopsis-guided selection reduce cost without missing the target?

Table 11 compares the static plan with four ways of using the synopsis at 𝜏 = 0.7: the mean rule, the coverage rule, and the budget rule at the static rate and at the requirement. Figure 7 shows, for each setting, the full trade-off between cost and violation rate as the coverage rule’s 𝜌 or the budget rule’s 𝜆 varies. Under the requirement, the synopsis lowers cost in every setting. Held to the requirement, at most 10% of queries missing the target, the budget rule is cheaper than the static plan in all 16 settings, at a median of 0.72× its cost, and recovers more than half of the saving that the optimum at the requirement achieves in a typical setting. Its violation rate on the held-out queries stays within the requirement in every setting; in half of them, the upper end of its confidence interval exceeds 10%, by at most a little over one percentage point. The comparison is fair because both selectors face the same requirement: the static plan misses less often than it is allowed to only because a catalog offers few configurations, and the synopsis spends that unused allowance on cheaper configurations where its estimates say they are safe. Figure 7 places each selector on the full trade-off curve, so that the comparison can also be read at any other violation rate. At the static plan’s own violation rate, it still saves in most settings. Held to the lower violation rate the static plan actually incurs, the budget rule has less room. Where that rate is reachable on 𝑄 (14 settings), it meets it on the held-out queries and is cheaper than the static plan in 12, by at least 8% in 10. It recovers a smaller share of the matched optimum’s saving, about a fifth in a typical setting. The simpler rules fall short. The mean rule is cheap only because it misses often: a cell mean at the target leaves many of the cell’s queries below it, and the rule misses the target on more than 10% of queries in most settings (italic). The coverage rule controls misses, as its calibration predicts, but not cost: requiring coverage 𝜌 in every cell rather than over the workload moves cells where the static plan’s configuration falls short to costlier ones, and it costs more than the static plan in nine settings (grey). Against the mean rule, its per-query shortfall is significantly lower in every setting (Wilcoxon–Pratt, Benjamini–Hochberg 𝑞 < 0.05), mostly because it misses far fewer queries; the queries it does miss fall less far below the target in half of the settings (†). The budget rule’s curve in Figure 7 lies on or below the coverage rule’s in most settings, so for a given violation budget it is the better way to use the synopsis.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

Static plan Model

Dir.

Viol. Short.

SigLIP2

i→i 0.8% i→t 10.1%§ t→i 2.6% t→t 3.4%

Synopsis, mean rule Cost Viol.

Synopsis, coverage rule (𝜌=0.9) Rec.

Cost

Viol.

Rec.

0.11 0.72 × [0.71, 0.72] 8.0% 89% 1.03 × [1.00, 1.05] 1.5% − 8% 0.14 0.30 × [0.24, 0.35] 19.5% 102% 0.62 × [0.56, 0.67] 8.6% 55% † 0.11 0.18 × [0.17, 0.19] 9.9% 103% 0.42 × [0.38, 0.46] 4.0% 73% 0.15 0.96 × [0.95, 0.99] 5.7% 29% 1.17 × [1.15, 1.20] 1.8% − 138%

Cost Viol. Rec.

Synopsis, budget ( ≤ 1−𝜌 ) Cost

Opt. cost

Viol. [95% CI] Rec. matched ≤ 1−𝜌

1.00 × [0.99, 1.02] 0.54 × [0.47, 0.60] 0.73 × [0.71, 0.75] 0.99 × [0.99, 1.00]

0.8% − 2% 0.69 × [0.68, 0.69] 9.6% [9.3, 9.9] 9.9% 67% 0.54 × [0.47, 0.60] 9.9% [8.5, 11.3] 2.6% 34% 0.14 × [0.14, 0.14] 9.9% [9.4, 10.4] 3.1% 6% 0.88 × [0.87, 0.89] 9.7% [9.3, 10.1]

82% 59% 96% 65%

0.68 × 0.31 × 0.20 × 0.87 ×

0.62 × 0.21 × 0.11 × 0.82 ×

2.1% − 218% 1.02 × [1.01, 1.03] 5.2% 39% 0.96 × [0.95, 0.96]‡ 3.4% 75% 0.70 × [0.67, 0.74] 2.2% 66% 0.82 × [0.81, 0.83]

2.5% − 9% 0.79 × [0.78, 0.79] 9.0% [8.7, 9.2] 2.9% 7% 0.53 × [0.52, 0.55] 9.2% [8.8, 9.6] 1.6% 37% 0.13 × [0.13, 0.14] 9.9% [9.4, 10.5] 0.9% 31% 0.42 × [0.41, 0.42] 9.3% [9.0, 9.7]

73% 62% 96% 89%

0.75 × 0.33 × 0.20 × 0.43 ×

0.71 × 0.24 × 0.10 × 0.34 ×

9.1% 2.8% 6.5% 8.2%

53% 0.78 × [0.78, 0.79] 9.8% [9.6, 10.1] 27% 0.39 × [0.39, 0.40] 9.1% [8.5, 9.9] − 6% 0.62 × [0.61, 0.63] 9.7% [9.1, 10.2] 14% 0.87 × [0.87, 0.88] 9.8% [9.5, 10.1]

50% 78% 55% 29%

0.62 × 0.30 × 0.39 × 0.61 ×

0.57 × 0.22 × 0.31 × 0.56 ×

9.1% 9.2% 7.2% 6.1%

27% 0.90 × [0.89, 0.90] 9.1% [8.9, 9.3] 21% 0.89 × [0.88, 0.91] 9.6% [8.9, 10.6] 22% 0.78 × [0.75, 0.81] 8.7% [8.2, 9.3] 21% 0.75 × [0.74, 0.75] 9.6% [9.4, 9.9]

23% 22% 30% 48%

0.61 × 0.60 × 0.37 × 0.54 ×

0.55 × 0.52 × 0.27 × 0.47 ×

OpenCLIP i→i i→t t→i t→t

2.5% 2.8% 1.6% 0.9%

0.12 0.85 × [0.84, 0.87] 9.0% 59% 1.54 × [1.50, 1.58] 0.13 0.35 × [0.33, 0.36] 19.6% 98% 0.74 × [0.73, 0.75] 0.09 0.17 × [0.16, 0.18] 11.5% 104% 0.40 × [0.36, 0.45] 0.11 0.44 × [0.43, 0.45] 9.2% 98% 0.62 × [0.61, 0.63]

i→i i→t t→i t→t

9.1% 2.8% 6.3% 8.4%

0.13 0.72 × [0.72, 0.73] 16.8% 0.13 0.31 × [0.30, 0.33] 25.0% 0.16 0.43 × [0.42, 0.44] 26.0% 0.20 0.76 × [0.75, 0.76] 22.3%

72% 1.03 × [1.02, 1.04] 4.9%† 98% 0.52 × [0.50, 0.53] 6.6%† 94% 0.67 × [0.66, 0.68] 9.8%† 63% 1.20 × [1.18, 1.22] 7.0%†

Qwen3-VL i→i i→t t→i t→t

9.9% 9.4% 7.4% 6.4%

0.13 0.77 × [0.76, 0.78] 17.7% 0.15 0.76 × [0.71, 0.84] 21.5% 0.30 0.48 × [0.43, 0.53] 22.6% 0.17 0.69 × [0.68, 0.71] 18.7%

59% 1.24 × [1.22, 1.26] 4.7%† − 62% 59% 1.48 × [1.41, 1.56] 5.8%† − 118% 83% 1.03 × [0.99, 1.10] 5.0% − 5% 67% 1.21 × [1.19, 1.24] 5.3%† − 46%

Jina-v4

Synopsis, budget (static viol.)

− 8% 0.80 × [0.79, 0.80] 69% 0.81 × [0.80, 0.83] 54% 1.04 × [1.03, 1.05]‡ − 52% 0.95 × [0.94, 0.95] 0.90 × [0.89, 0.90] 0.92 × [0.90, 0.93] 0.86 × [0.84, 0.88] 0.90 × [0.89, 0.92]

Table 11: Plan selection at 𝜏 = 0.7 (𝐾 = 10,000). Costs are relative to the static plan, include the lookup, and carry 95% confidence intervals. Bold: our method, the budget rule at the requirement; grey: not cheaper than the static plan; italic: violation rate above the requirement of 10%. Terms and markers: Table 6.

All rules differ significantly from the static plan in which queries they miss (McNemar), in all but three of the 64 comparisons. Where the synopsis gains little. At the static rate, the synopsis saves nothing for SigLIP2 and OpenCLIP i→i, although the optimum would save a quarter to a third: the only cheaper configuration, hnsw_low, serves part of the queries, and the synopsis cannot single out which ones reliably enough. More generally, half of the variation in fidelity lies within cells (RQ2), where the synopsis cannot see it, which is why the budget rule captures only part of the optimum’s saving. Other targets. At 𝜏 = 0.8 and 0.9, the requirement can be met on 𝑄 in 14 and 6 settings respectively; in the others, no configuration meets the target on 90% of queries. Where it can be met, the budget rule at the requirement is cheaper than the static plan in every setting. Answer to RQ4. Yes, under the requirement a static deployment is built to meet: synopsis-guided selection lowers cost in every setting, to a median of 0.72× the static plan, lookup included. Even at the static plan’s lower realized violation rate, it lowers cost in most settings. The simpler rules show why the budget rule is needed: the cell mean ignores how fidelity is spread within a cell, and per-cell coverage overpays in hard cells.

reaches 0.7 and 0.8 (efSearch of 192 and 384 for SigLIP2, 256 and 1,024 for OpenCLIP, 48 and 96 for Jina-v4, and 64 and 128 for Qwen3-VL). All three share one index, so per-query selection adds no memory. Their costs were measured on one node together with hnsw_high and put on the scale of the main benchmark through it. • Union: the nine configurations plus the single index’s two lower settings, eleven configurations with no additional index. Its static plan is the best static choice among everything we built, the strongest static baseline available without new indexes. For each catalog, the static plan, the optimum, and the synopsis are computed within that catalog alone, so that a static and a per-query deployment choose among the same configurations. The synopsis uses the same landmarks; only the configurations it records change. Table 12 reports every cost relative to the static plan of the nineconfiguration catalog, so that all catalogs share one scale.

5.4.1 Does the saving need the full catalog? Per-query selection requires every configuration it may choose to be built and kept in memory. Our nine-configuration catalog occupies 140–376 GB per model, most of it in the three HNSW indexes (Table 13). We ask how much of the saving survives with less, using two smaller catalogs and one larger one:

Against the strongest static baseline, the synopsis still saves. The union’s static plan is the nine-configuration static plan in 12 of 16 settings: the cheaper single-index settings do not help a static deployment there, because its hardest queries still need the same configuration. In the other four, the union’s static plan is a cheap single-index setting, which shows that hnsw_low is a poor operating point for these models. Measured against the union’s own static plan, the budget rule at the requirement costs a median of 0.70×, about the same as with the nine-configuration catalog. It is cheaper in 13 settings, equal in one, and slightly costlier, by about its lookup cost, in the two where the union’s static plan is already its cheapest setting (grey in Table 12).

• HNSW-only: the three HNSW configurations, still three separately built indexes. • Single index: the index of hnsw_high, searched with three values of efSearch. The highest is hnsw_high’s own; the two lower ones are, per model, the first values of the parameter sweep at which mean fidelity over the four directions

A smaller catalog keeps most of the opportunity. Without the IVFfamily indexes, the optimum keeps most of the full catalog’s saving in a typical setting. The loss lies in Jina-v4 and Qwen3-VL, whose low and moderate IVF tiers are cheaper than hnsw_mod, and in SigLIP2 and OpenCLIP i→t, where only IVF-family configurations meet the target often enough to stay within the requirement. The

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

cost / static plan

SigLIP2 i→i · static hnsw mod

SigLIP2 i→t · static oivfpq high

1.0 0.8

0.8

0.8

0.6

0.6

0.6

0.75

0.4

0.4

0.4

0.50

0.2

0.2

0.2

0.25

0.0 0.0

2.5

5.0

7.5

10.0

12.5

cost / static plan

1.5

1.0

0.5

0.0 0.0

2.5

5.0

7.5

10.0

1.00

0.0 0

OpenCLIP i→i · static hnsw mod

10

20

0.00 0

OpenCLIP i→t · static oivfpq high

5

10

0.0

OpenCLIP t→i · static hnsw high

1.0

1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.2

0.2

0.2

0.0

0.0

12.5

0

10

20

5

10

0.0

Jina-v4 t→i · static hnsw high 1.0

0.8

0.8

0.8

0.6

0.6

0.6

0.4

0.4

0.4

0.50

0.2

0.2

0.2

0.25

0.0 5

10

15

20

Qwen3-VL i→i · static ivfpq mod

10

20

30

1.5

1.25

0.75 0.50

0.5

0.25 0.00

0.0 0

5

10

15

20

20

30

violation rate (%)

10

20

violation rate (%)

7.5

10.0

12.5

10

20

Qwen3-VL t→t · static hnsw mod

1.25 1.00

0.6

0.75

0.4

0.50

0.2

0.25

0.0 0

0

Qwen3-VL t→i · static hnsw high

0.8

1.0

5.0

0.00 10

1.0

1.00

2.5

0.75

0

Qwen3-VL i→t · static hnsw mod

12.5

1.00

0.0 0

10.0

1.25

1.0

0

7.5

Jina-v4 t→t · static hnsw mod

1.0

0.0

5.0

0.0 0

Jina-v4 i→t · static hnsw high

2.5

OpenCLIP t→t · static oivfpq low

1.0

Jina-v4 i→i · static ivfpq mod cost / static plan

SigLIP2 t→t · static hnsw mod 1.25

1.0

0.0

cost / static plan

SigLIP2 t→i · static hnsw high

1.0

0.00 0

10

20

violation rate (%)

coverage rule (ρ varies)

coverage rule, ρ = 0.9

budget rule, λ at static viol.

static plan

budget rule (λ varies)

mean rule

budget rule, λ at ≤ 1 − ρ

matched optimum

0

5

10

15

20

violation rate (%)

optimum at ≤ 1 − ρ

Figure 7: Cost against violation rate on the held-out queries (𝜏 = 0.7, 𝐾 = 10,000) as 𝜌 (coverage rule) or 𝜆 (budget rule) varies. Markers: static plan, mean rule, coverage rule at 𝜌 = 0.9, budget rule at the static rate (open square) and at the requirement (filled square), matched optimum (open star), and optimum at the requirement (filled star). Dotted: the static plan’s violation rate; dashed: the requirement. single index differs from the full catalog in both directions: its lower settings are cheaper and more accurate than hnsw_low for SigLIP2, OpenCLIP, and Jina-v4, but its single grid of efSearch values per model leaves the lower settings short of the target in some directions, where the only remaining choice is hnsw_high’s expensive setting, and in three settings no assignment meets the requirement.

The synopsis captures it within each catalog. Within each smaller catalog, the budget rule at the requirement is cheaper than that catalog’s own static plan in most settings where the requirement can be met, by about a fifth with three HNSW indexes and about a third with a single index (Table 13). With a single index, this saving needs no additional memory, and labeling the construction sample costs far less, since only three configurations are run. Where the single index’s static plan is already its cheapest setting (SigLIP2 and

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

Full catalog (nine indexes)

HNSW-only (three indexes)

Budget, ≤ 1−𝜌 Budget Model

Dir. Static

Opt.

Cost

Viol. static v. Static

SigLIP2

i→i H-m i→t O-h∗ t→i H-h t→t H-m

0.62 × 0.21 × 0.11 × 0.82 ×

0.69 × 0.54 × 0.14 × 0.88 ×

9.6% 9.9% 9.9% 9.7%

OpenCLIP i→i H-m i→t O-h t→i H-h t→t O-l

0.71 × 0.24 × 0.10 × 0.34 ×

0.79 × 0.53 × 0.13 × 0.42 ×

i→i I-m i→t H-h t→i H-h t→t H-m

0.57 × 0.22 × 0.31 × 0.56 ×

Qwen3-VL i→i I-m i→t H-m t→i H-h t→t H-m

0.55 × 0.52 × 0.27 × 0.47 ×

Jina-v4

Single index (three efSearch)

Budget, ≤ 1−𝜌 Budget

Viol. static v. Static

Opt.

Cost

Viol. / static

9.6% 1.01 × l 12.1% 0.65‡ × h∗ 9.5% 0.81‡ × h 9.7% 1.01 × h

0.21 × 0.22 × infeas. 0.68‡ × 0.16 × 0.38 × 0.28 × 0.62 ×

6.9% 0.22 × S-l 12.1% 0.68‡ × O-h∗ 9.9% 0.98‡ × H-h 9.5% 6.55‡ × H-m

0.21 × 0.18 × 0.04 × 0.22 ×

0.22 × 0.54 × 0.15 × 0.35 ×

6.9% 9.9% 9.4% 9.8%

1.07 × 0.54 × 0.15 × 0.35 ×

9.0% 1.02 × H-m 0.71 × 0.79 × 9.2% 0.96‡ × H-h∗ infeas. 0.46‡ × 9.9% 0.70 × H-h 0.10 × 0.15 × 9.3% 0.82 × H-m∗ 0.39 × 1.08‡ ×

9.0% 1.04 × 25.3% 0.19 × 9.3% 0.80‡ × 10.7% 0.40 ×

0.32 × 0.34 × infeas. 0.61‡ × 0.05 × 0.13 × infeas. 2.95‡ ×

7.9% 0.34 × S-l 30.8% 0.61‡ × O-h 9.6% 0.14 × S-m 20.3% 2.95‡ × O-l

0.32 × 0.20 × 0.05 × 0.18 ×

0.34 × 0.52 × 0.13 × 0.32 ×

7.9% 9.4% 9.5% 9.7%

1.08 × 0.52 × 1.00 × 0.32 ×

0.78 × 0.39 × 0.62 × 0.87 ×

9.8% 0.80 × 9.1% 0.81 × 9.7% 1.04‡ × 9.8% 0.95 ×

H-m H-h H-h H-m

0.63 × 0.28 × 0.38 × 0.70 ×

0.81 × 0.41 × 0.64 × 1.00 ×

9.9% 1.07 × m 9.9% 0.90‡ × h 9.8% 0.96‡ × h 9.6% 1.05 × h

0.44 × 0.25 × 0.34 × 0.51 ×

0.60 × 0.46 × 0.71 × 0.96 ×

9.6% 0.71 × S-m 9.1% 0.98‡ × H-h 9.9% 1.01‡ × H-h 9.5% 2.33‡ × H-m

0.44 × 0.19 × 0.26 × 0.42 ×

0.59 × 0.39 × 0.63 × 0.83 ×

9.7% 8.9% 9.5% 9.4%

0.80 × 0.39 × 0.63 × 0.83 ×

0.90 × 0.89 × 0.78 × 0.75 ×

9.1% 9.6% 8.7% 9.6%

0.90 × 0.92 × 0.86 × 0.90 ×

H-m H-m H-h H-m

0.72 × 0.81 × 0.35 × 0.73 ×

1.03 × 1.04 × 0.82 × 0.95 ×

9.0% 1.39 × 9.7% 1.06 × 9.9% 1.00‡ × 9.7% 1.05 ×

0.58 × 0.71 × 0.41 × 0.48 ×

0.70 × 1.48 × 0.86 × 0.83 ×

9.6% 0.99 × I-m 9.0% 3.23‡ × H-m 9.7% 1.00‡ × H-h 9.5% 3.25‡ × H-m

0.47 × 0.42 × 0.24 × 0.38 ×

0.70 × 0.89 × 0.78 × 0.70 ×

9.6% 9.6% 8.9% 9.5%

0.70 × 0.89 × 0.78 × 0.70 ×

H-m H-h∗ H-h H-m

Cost

0.62 × 0.69 × infeas. 0.65‡ × 0.11 × 0.15 × 0.82 × 0.88 ×

Viol. static v. Static

l h∗ m h∗

m h h h

Opt.

Budget, ≤ 1−𝜌 Budget

Cost

1.00 × 0.54 × 0.73 × 0.99 ×

Opt.

Union (eleven configurations)

Budget, ≤ 1−𝜌 Budget

Table 12: Plan selection with smaller catalogs and their union at 𝜏 = 0.7. All costs are relative to the static plan of the nineconfiguration catalog, except the last column, which is relative to the union’s own static plan (bold: cheaper; grey: not cheaper). Abbreviations and markers: Table 6.

Full

HNSW

Single

Union

Indexes per collection 9 3 1 9 Memory (GB), SigLIP2 208.7 163.9 55.2 208.7 Memory (GB), OpenCLIP 140.4 110.4 37.4 140.4 Memory (GB), Jina-v4 375.8 288.7 96.8 375.8 Memory (GB), Qwen3-VL 375.8 288.7 96.8 375.8 Labeling 𝑄 (CPU-h) 344–5,036 94–767 84–705 369–5,086 Opt., median 0.41 × 0.63 × (14) 0.34 × (13) 0.23 × Budget, median 0.72 × 0.81 × (13) 0.62 × (13) 0.53 × Budget / own static, med. 0.72 × 0.78 × (13) 0.68 × (13) 0.70 ×

Table 13: The catalogs of Section 5.4.1. Memory: image and text indexes together; the union adds no index. Costs: medians over the settings where the catalog can meet the requirement (their number in parentheses where fewer than 16), relative to the nine-configuration static plan, except the last row, which is relative to each catalog’s own static plan.

OpenCLIP i→i), and for OpenCLIP t→i, the synopsis saves nothing and costs 3–8% more, mostly its lookup; where the static plan is the middle setting for Jina-v4 and Qwen3-VL i→i, it still saves 19% and 32%. Summary. The saving does not depend on a large catalog or a weak static baseline. Against the best static choice among all indexes we built, the synopsis still costs a median of 0.70×; a single HNSW index searched at three settings, a quarter of the full catalog’s memory, lets the synopsis save within that index alone. The single index is not a uniform substitute for the full catalog, however: with one grid of efSearch values per model it cannot meet the requirement in three settings, and per setting it is much cheaper or much costlier than the full catalog.

SigLIP2 OpenCLIP Jina-v4 Qwen3-VL Dimension 𝑑 𝑐 est , 1 query, mean (𝜇 s) 𝑐 est , 1 query, p99 (𝜇 s) Cheapest plan, 1 query (𝜇 s) 𝑐 est , batched (𝜇 s/q) Cheapest plan, batched (𝜇 s/q) Synopsis size (MiB) 𝑘 -means (GPU-h) Exact 𝑘 -NN on 𝑄 (GPU-h) All configs on 𝑄 (h, 64 thr.) All configs on 𝑄 (CPU-h)

1152 1640 1659 1678 23.3 665 119.5 0.12 0.57 78.7 5,036

768 822 848 1482 20.6 490 90.2 0.08 0.40 51.2 3,275

2048 2859 2874 445 31.4 223 187.8 0.21 0.98 5.4 344

2048 2842 2873 349 32.3 163 187.8 0.20 0.98 8.8 563

Table 14: Cost of the synopsis at 𝐾 = 10,000, averaged over directions: the lookup, one query at a time and batched, against the cheapest configuration (hnsw_low); the synopsis’s size; and the one-time offline cost. Bold: the batched regime used throughout; italic: single-query lookup costlier than the cheapest configuration.

5.5

RQ5: What does the synopsis cost, and how sensitive is it to its parameters?

Lookup cost. In the batched regime used throughout, the lookup takes 21–32 𝜇s per query (Table 14), at most a fifth of the cheapest configuration’s cost, and it is included in every cost of Table 11. One query at a time, it is dominated by the exact scan of the 𝐾 landmarks: it costs less than hnsw_low for OpenCLIP and SigLIP2, but several times as much for the 2,048-dimensional Jina-v4 and Qwen3-VL (italic). For single queries at this 𝐾, a faster nearestlandmark search, such as an approximate index over the landmarks, is needed; we leave it to future work. Size and construction. The synopsis occupies 90–188 MiB, mostly the landmarks themselves, well under 1% of the HNSW indexes of

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

𝐾

Skill

Thin

Size (MiB)

1 0.000 – <0.1 500 0.280 0.01% 4.5–9.4 1,250 0.335 0.02% 11.3–23.5 2,500 0.374 0.04% 22.5–47.0 5,000 0.416 0.14% 45.1–93.9 10,000 0.451 0.51% 90.2–187.8 20,000 0.469 2.17% 180.4–375.7 25,000 0.468 3.61% 225.4–469.6 40,000 0.440 10.46% 360.7–751.3

Table 15: Sensitivity to the number of landmarks 𝐾 over the 16 settings (𝐾 = 1 is a single cell, the global average). Skill: mean over settings of the mean over all nine configurations. Bold: the default. Thin: held-out queries in cells with fewer than 𝑞 min sample queries. Terms: Table 6.

a single tier. Building it requires a few minutes of GPU time for clustering and an hour or less for exact search on 𝑄, shared by all configurations. Running every configuration on 𝑄 dominates the offline cost, most of all for SigLIP2 and OpenCLIP, whose IVF-family configurations probe thousands of partitions; with a single index (Section 5.4.1), it is several times cheaper. This cost is paid once per model and catalog. Number of landmarks. Skill rises with 𝐾 up to about 20,000 landmarks and then falls, as more held-out queries land in cells with fewer than 𝑞 min sample queries (Table 15). Lookup cost and synopsis size grow linearly with 𝐾; our default of 10,000 is close to the best skill at half the cost of 20,000. Construction sample. The synopsis needs a large construction sample at this 𝐾: built from 10% of 𝑄, most held-out queries fall into sparse cells and skill drops by more than half, and with 1% the synopsis is barely better than the global average. Roughly 70 sample queries per cell are needed. The minimum support matters less: 𝑞 min = 1 leaves skill unchanged, while 𝑞 min = 50 lowers it. Answer to RQ5. The synopsis is small, and its batched lookup costs at most a fifth of the cheapest configuration; its one-time construction is dominated by running the catalog on the construction sample, which needs several hundred thousand queries per direction at 𝐾 = 10,000. Accuracy grows with 𝐾 as long as cells keep enough sample queries. A single-query lookup by exact landmark scan is too slow for 2,048-dimensional models.

6

RELATED WORK

Approximate nearest-neighbor indexes and their tuning. Graphbased indexes such as HNSW [32] and DiskANN [24], and partitionand quantization-based ones such as IVF with product quantization [11, 17], SPANN [8], and ScaNN [15], cover a wide range of trade-offs between cost and fidelity. Benchmarks and surveys compare them by their average recall over a workload [3, 35, 44], and tuners such as VDTuner [48] search index types and parameters for a workload-level target of throughput and recall. All of these choose one configuration for a workload; they produce a better static plan.

Our synopsis takes a catalog as given and chooses among its configurations per query. The two are complementary: a better-tuned catalog gives the synopsis better options, as the union catalog of Section 5.4.1 shows. Adaptive search within an index. Learned adaptive early termination [27] predicts, per query, when a search has found its neighbors, and DARTH [5] terminates a search once a declared target recall is predicted to be met. Both adapt how long a search runs inside an index that has already been chosen, and both need that index to be able to reach the target. Plan selection makes the earlier decision, which index and which settings to use, before any search runs, and it can move a query to a different index family when the default one cannot reach the target. The approaches compose: an early-termination method can run inside whichever configuration the synopsis selects. Query hardness. Local intrinsic dimensionality [4] and Steinerhardness [45] characterize how hard a query is for nearest-neighbor search, the latter for graph indexes specifically, and work on crossmodal search observes that queries of one modality lie outside the distribution of the other [7, 29]. These measures explain why some queries are hard, but they are not calibrated estimates of whether a particular configuration will meet a particular target, which is what plan selection needs. The synopsis measures that quantity directly, per region and per configuration; in our experiments, local density alone predicts fidelity much less well (Section 5.2). Cardinality estimation and synopses. Cost-based optimizers choose among access paths using estimates of each plan’s output size [40], obtained from synopses such as histograms built offline and consulted at plan time [16], and more recently from learned models [23]; the quality of these estimates largely determines the quality of the chosen plans [25]. The fidelity synopsis applies this design to vector search, with cells of the embedding space as buckets and fidelity as the statistic. Unlike selectivity, which is a property of the data and the predicate, fidelity also depends on the physical plan, so the synopsis is keyed by configuration as well as by region. Accuracy-aware query processing. A broad line of work trades accuracy for cost under an explicit target: approximate query processing with error bounds [2], including over multimodal data [18]; cheap filters and model cascades for machine-learning inference [20, 31]; cascades and routing among language models [6]; and optimizers for semantic operators that choose models and plans for cost and quality [30, 36, 41]. Our work brings this view to the vectorsearch operator itself, with a per-query choice among physical configurations and a workload-level requirement on how often the fidelity target may be missed. Vector search in database systems. Vector databases and extensions such as Milvus [43], AnalyticDB-V [46], and pgvector [1] expose index types and search parameters, typically as settings for a collection or session [35]. Work on hybrid queries, such as VBase [50] and ACORN [37], chooses how to combine vector search with relational predicates, based on the predicates’ selectivity. To our knowledge, no system chooses the vector-search configuration itself per query from an estimate of its fidelity.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

7

LIMITATIONS AND CONCLUSION

Limitations. Half of the variation in fidelity lies within cells, so the synopsis captures only part of the per-query optimum’s saving, and less when held to the static plan’s realized violation rate than to the requirement. The comparison at the requirement lets the synopsis spend an allowance the static plan leaves unused; we report the stricter comparison as well. Building the synopsis requires labeling a large construction sample with every configuration, a one-time cost that is substantial for a large catalog and much smaller for a single index. With an exact scan of the landmarks, the single-query lookup is too slow for high-dimensional models. Finally, the size of the opportunity depends on the catalog: part of it, for some models, comes from how the catalog’s HNSW tiers were built, although the synopsis’s advantage persists against the best static choice among all the indexes we built. Future work. Three directions follow directly. A faster nearestlandmark search, such as an approximate index over the landmarks, would make single-query lookups cheap for high-dimensional models. Search-parameter grids chosen per query direction, rather than per model, would remove the coarse steps that limited the singleindex catalog. And reducing the labeling cost, by sampling cells adaptively or by transferring a synopsis between catalogs that share an index, would make the synopsis cheaper to build and to keep current as the corpus changes. Conclusion. A static ANN deployment must be sized for its hardest queries and therefore overpays for the rest. We showed that a query’s location in the embedding space predicts how each configuration will perform on it, that this prediction must be kept per configuration, and that a compact synopsis of it, consulted with a single nearest-landmark lookup, lets an optimizer choose configurations per query while meeting the same requirement as a static deployment, at a median of 0.72× its cost. The saving persists against the best static choice among the same indexes and within a single index. A fidelity synopsis is to vector search what a histogram is to relational selectivity estimation: a statistic built once, offline, that an optimizer consults before executing any plan.

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search

REFERENCES [1] pgvector: Open-source vector similarity search for Postgres. https://github.com/ pgvector/pgvector. [2] Sameer Agarwal, Barzan Mozafari, Aurojit Panda, Henry Milner, Samuel Madden, and Ion Stoica. BlinkDB: Queries with bounded errors and bounded response times on very large data. In Eighth Eurosys Conference 2013, EuroSys ’13, pages 29–42, 2013. [3] Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Inf. Syst., 87:101374, 2020. [4] Martin Aumüller and Matteo Ceccarello. The role of local dimensionality measures in benchmarking nearest neighbor search. Inf. Syst., 101:101807, 2021. [5] Manos Chatzakis, Yannis Papakonstantinou, and Themis Palpanas. DARTH: Declarative recall through early termination for approximate nearest neighbor search. Proc. ACM Manag. Data, 3(4):242:1–242:26, 2025. [6] Lingjiao Chen, Matei Zaharia, and James Zou. FrugalGPT: How to use large language models while reducing cost and improving performance. CoRR, abs/2305.05176, 2023. [7] Meng Chen, Kai Zhang, Zhenying He, Yinan Jing, and X. Sean Wang. RoarGraph: A projected bipartite graph for efficient cross-modal approximate nearest neighbor search. Proc. VLDB Endow., 17(11):2735–2749, 2024. [8] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: highly-efficient billion-scale approximate nearest neighborhood search. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 5199–5212, 2021. [9] Wei Chen, Jincai Chen, Fuhao Zou, Yuan-Fang Li, Ping Lu, Qiang Wang, and Wei Zhao. Vector and line quantization for billion-scale similarity search on gpus. Future Gener. Comput. Syst., 99:295–307, 2019. [10] Mehdi Cherti, Romain Beaumont, Ross Wightman, Mitchell Wortsman, Gabriel Ilharco, Cade Gordon, Christoph Schuhmann, Ludwig Schmidt, and Jenia Jitsev. Reproducible scaling laws for contrastive language-image learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023, pages 2818–2829. IEEE, 2023. [11] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. Optimized product quantization. IEEE Trans. Pattern Anal. Mach. Intell., 36(4):744–755, 2014. [12] W Brier Glenn et al. Verification of forecasts expressed in terms of probability. Monthly weather review, 78(1):1–3, 1950. [13] Michael Günther, Saba Sturua, Mohammad Kalim Akram, Isabelle Mohr, Andrei Ungureanu, Bo Wang, Sedigheh Eslami, Scott Martens, Maximilian Werk, Nan Wang, and Han Xiao. jina-embeddings-v4: Universal embeddings for multimodal multilingual retrieval. In David Ifeoluwa Adelani, Catherine Arnett, Duygu Ataman, Tyler A. Chang, Hila Gonen, Rahul Raja, Fabian Schmidt, David Stap, and Jiayi Wang, editors, Proceedings of the 5th Workshop on Multilingual Representation Learning (MRL 2025), pages 531–550, Suzhuo, China, November 2025. Association for Computational Linguistics. [14] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q Weinberger. On calibration of modern neural networks. In International conference on machine learning, pages 1321–1330. PMLR, 2017. [15] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 3887–3896. PMLR, 2020. [16] Yannis E. Ioannidis. The history of histograms (abridged). In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB), pages 19–30, 2003. [17] Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1):117–128, 2011. [18] Saehan Jo and Immanuel Trummer. Thalamusdb: Approximate query processing on multi-modal data. Proc. ACM Manag. Data, 2(3):186, 2024. [19] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. CoRR, abs/1702.08734, 2017. [20] Daniel Kang, John Emmons, Firas Abuzaid, Peter Bailis, and Matei Zaharia. NoScope: Optimizing deep CNN-based queries over video streams at scale. Proc. VLDB Endow., 10(11):1586–1597, 2017. [21] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, 2020, pages 6769–6781. Association for Computational Linguistics, 2020. [22] Omar Khattab and Matei Zaharia. Colbert: Efficient and effective passage search via contextualized late interaction over BERT. In Jimmy X. Huang, Yi Chang,

Xueqi Cheng, Jaap Kamps, Vanessa Murdock, Ji-Rong Wen, and Yiqun Liu, editors, Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pages 39–48. ACM, 2020. [23] Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. Learned cardinalities: Estimating correlated joins with deep learning. In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, 2019. [24] Ravishankar Krishnaswamy, Magdalen Dobson Manohar, and Harsha Vardhan Simhadri. The diskann library: Graph-based indices for fast, fresh and filtered vector search. IEEE Data Eng. Bull., 48(3):20–42, 2024. [25] Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter A. Boncz, Alfons Kemper, and Thomas Neumann. How good are query optimizers, really? Proc. VLDB Endow., 9(3):204–215, 2015. [26] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, Sebastian Riedel, and Douwe Kiela. Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), 2020. [27] Conglong Li, Minjia Zhang, David G. Andersen, and Yuxiong He. Improving approximate nearest neighbor search through learned adaptive early termination. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pages 2539–2554, 2020. [28] Mingxin Li, Yanzhao Zhang, Dingkun Long, Keqin Chen, Sibo Song, Shuai Bai, Zhibo Yang, Pengjun Xie, An Yang, Dayiheng Liu, Jingren Zhou, and Junyang Lin. Qwen3-vl-embedding and qwen3-vl-reranker: A unified framework for state-of-the-art multimodal retrieval and ranking. CoRR, abs/2601.04720, 2026. [29] Weixin Liang, Yuhui Zhang, Yongchan Kwon, Serena Yeung, and James Zou. Mind the gap: Understanding the modality gap in multi-modal contrastive representation learning. In Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 2022. [30] Chunwei Liu, Matthew Russo, Michael J. Cafarella, Lei Cao, Peter Baile Chen, Zui Chen, Michael J. Franklin, Tim Kraska, Samuel Madden, and Gerardo Vitagliano. A declarative system for optimizing AI workloads. CoRR, abs/2405.14696, 2024. [31] Yao Lu, Aakanksha Chowdhery, Srikanth Kandula, and Surajit Chaudhuri. Accelerating machine learning inference with probabilistic predicates. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD 2018, pages 1493–1508, 2018. [32] Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell., 42(4):824–836, 2020. [33] Allan H Murphy. Skill scores based on the mean square error and their relationships to the correlation coefficient. Monthly weather review, 116(12):2417–2424, 1988. [34] Mahdi Pakdaman Naeini, Gregory Cooper, and Milos Hauskrecht. Obtaining well calibrated probabilities using bayesian binning. In Proceedings of the AAAI conference on artificial intelligence, volume 29, 2015. [35] James Jie Pan, Jianguo Wang, and Guoliang Li. Survey of vector database management systems. VLDB J., 33(5):1591–1615, 2024. [36] Liana Patel, Siddharth Jha, Carlos Guestrin, and Matei Zaharia. LOTUS: enabling semantic queries with llms over tables of unstructured and structured data. CoRR, abs/2407.11418, 2024. [37] Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. Proc. ACM Manag. Data, 2(3):120, 2024. [38] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. Learning transferable visual models from natural language supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 8748–8763. PMLR, 2021. [39] Christoph Schuhmann, Richard Vencu, Romain Beaumont, Robert Kaczmarczyk, Clayton Mullis, Aarush Katta, Theo Coombes, Jenia Jitsev, and Aran Komatsuzaki. LAION-400M: open dataset of clip-filtered 400 million image-text pairs. CoRR, abs/2111.02114, 2021. [40] Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, and Thomas G. Price. Access path selection in a relational database management system. In Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pages 23–34, 1979. [41] Shreya Shankar, Tristan Chambers, Tarak Shah, Aditya G. Parameswaran, and Eugene Wu. Docetl: Agentic query rewriting and evaluation for complex document processing. Proc. VLDB Endow., 18(9):3035–3048, 2025. [42] Michael Tschannen, Alexey Gritsenko, Xiao Wang, Muhammad Ferjad Naeem, Ibrahim Alabdulmohsin, Nikhil Parthasarathy, Talfan Evans, Lucas Beyer, Ye Xia, Basil Mustafa, et al. Siglip 2: Multilingual vision-language encoders with improved semantic understanding, localization, and dense features. arXiv preprint arXiv:2502.14786, 2025.

Adithya Ramanatha, Sanskar S. Singh, and Maya Ramanath

[43] Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. Milvus: A purpose-built vector data management system. In Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data, pages 2614–2627, 2021. [44] Mengzhao Wang, Xiaoliang Xu, Qiang Yue, and Yuxiang Wang. A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow., 14(11):1964–1978, 2021. [45] Zeyu Wang, Qitong Wang, Xiaoxing Cheng, Peng Wang, Themis Palpanas, and Wei Wang. Steiner-hardness: A query hardness measure for graph-based ANN indexes. Proc. VLDB Endow., 17(13), 2024. [46] Chuangxian Wei, Bin Wu, Sheng Wang, Renjie Lou, Chaoqun Zhan, Feifei Li, and Yuanzhe Cai. AnalyticDB-V: A hybrid analytical engine towards query fusion for structured and unstructured data. Proc. VLDB Endow., 13(12):3152–3165, 2020. [47] Mengyao Xu, Gabriel de Souza Pereira Moreira, Ronay Ak, Radek Osmulski, Yauhen Babakhin, Zhiding Yu, Benedikt Schifferer, and Even Oldridge. Llama

nemoretriever colembed: Top-performing text-image retrieval model. CoRR, abs/2507.05513, 2025. [48] Tiannuo Yang, Wen Hu, Wangqi Peng, Yusen Li, Jianguo Li, Gang Wang, and Xiaoguang Liu. VDTuner: Automated performance tuning for vector data management systems. In 40th IEEE International Conference on Data Engineering, ICDE 2024, 2024. [49] Xiaohua Zhai, Basil Mustafa, Alexander Kolesnikov, and Lucas Beyer. Sigmoid loss for language image pre-training. In IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023, pages 11941–11952. IEEE, 2023. [50] Qianxi Zhang, Shuotao Xu, Qi Chen, Guoxin Sui, Jiadong Xie, Zhizhen Cai, Yaoqi Chen, Yinxuan He, Yuqing Yang, Fan Yang, Mao Yang, and Lidong Zhou. VBase: Unifying online vector similarity search and relational queries via relaxed monotonicity. In 17th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2023, pages 377–395, 2023.

Related documents

• Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search#1534582
• Scalable s-step Preconditioned Conjugate Gradient with Chebyshev Basis and Gauss-Seidel Gram Solve#998136
• SmartANN: Object Causal Modeling Boosts Approximate Nearest Neighbor Diagnosis and Auto-Design#985612
• Cost Comparisons for Random and Deterministic Scans in Component-Wise Markov Chains#1156056
• Coverage Is Not Redundancy: Maintenance Cost and Exposure of Query-Aware Admission Indexes in Vector Databases Under Workload Drift#617713