TL;DR
This paper introduces Fidelity Synopses, a novel approach to optimize vector search by predicting per-query performance before execution. By dividing the embedding space into regions and recording historical performance, the system can dynamically choose the cheapest index configuration that meets a user's accuracy target, reducing search costs by a median of 28% compared to traditional static deployments.
What Problem Does This Paper Address?
Approximate Nearest Neighbor (ANN) search is the backbone of modern AI applications like retrieval-augmented generation (RAG) and multimodal search. However, ANN indexes (like HNSW or IVF) force a trade-off between cost (latency/compute) and fidelity (the fraction of true nearest neighbors returned).
Currently, most systems use a "one-size-fits-all" approach: they pick a single index configuration offline that works well on average or handles the "hardest" queries. This leads to massive over-provisioning. Easy queries are run on expensive, high-fidelity plans they don't need, while a small "tail" of difficult queries (often cross-modal ones, like searching images with text) might still fail to meet accuracy targets.
The challenge is that we can't easily know how "hard" a query is until we've already done the expensive work of finding its neighbors. The authors aim to bring the concept of query optimization—a staple of relational databases—to the world of vector search.
Methods
The authors propose the Fidelity Synopsis, which functions much like a histogram in a traditional database optimizer.
The Offline Phase: Building the Map
- Landmarks: The system clusters the corpus embeddings into $K$ "cells" using spherical k-means. These landmarks act as representative points for different regions of the embedding space.
- Labeling: A sample of queries is run through every available index configuration in the catalog. The system records the exact fidelity (recall) achieved by each configuration for every query.
- Aggregation: For each cell and each configuration, the synopsis stores a histogram of these fidelity scores. This tells us, for example, "In this region of space, HNSW with
efSearch=64hits 70% recall 90% of the time."
The Online Phase: Picking the Plan
When a new user query arrives:
- Locate: The system finds the query's nearest landmark (identifying its cell).
- Estimate: It reads the fidelity distributions for that cell across all configurations.
- Select (The Budget Rule): An optimizer picks the configuration that minimizes cost while ensuring the overall workload meets a "reliability" target (e.g., "at most 10% of queries should miss the fidelity target").
Datasets
The evaluation uses a benchmark of 5.8 million image-caption pairs from the LAION-400M dataset. To ensure the results generalize, the authors tested four different embedding models:
- Dual Encoders: SigLIP2 and OpenCLIP.
- Vision-Language Models (VLMs): Jina-v4 and Qwen3-VL.
The experiments cover four query directions: image-to-image, text-to-text, and the more challenging cross-modal image-to-text and text-to-image directions.
Key Insights and Ideas
- Smoothness Premise: The core idea works because fidelity is "smooth"—queries that are close together in the embedding space tend to behave similarly under the same index.
- Configuration Specificity: You can't just have a single "difficulty" score for a region. A region might be easy for a graph-based index (HNSW) but hard for a quantization-based index (IVF) due to how they partition space. The synopsis must be keyed by both region and configuration.
- The Cross-Modal Tail: The "opportunity" for saving is greatest in cross-modal search. Because text and image embeddings often live in slightly different parts of the space, these queries are "harder" and drive up the cost of static plans. Per-query selection allows the system to use cheaper plans for the easier uni-modal queries.
- Single-Index Optimization: You don't need to build nine different physical indexes to save money. The system can achieve significant gains just by dynamically tuning search-time parameters (like HNSW's
efSearch) within a single index.
Key Results
- Cost Savings: Synopsis-guided selection lowered costs in all 16 tested settings (4 models × 4 directions). The median cost was 0.72x that of a static deployment.
- Efficiency: The overhead of looking up the synopsis is tiny—roughly 21–32 microseconds per query when batched, which is a small fraction of the search time itself.
- Calibration: The synopsis's estimates are well-calibrated; if it predicts an 80% chance of meeting a target, roughly 80% of queries actually do.
As shown in the table below, for many models, the vast majority of queries could be served by plans costing less than a third of the static plan:
Limitations and Future Work
- Intra-cell Variation: The synopsis currently captures about half of the variation in fidelity. The other half happens within the cells, which the current landmark approach can't see.
- High-Dimensionality Lookup: For very high-dimensional models (2,048+ dimensions), a simple linear scan of 10,000 landmarks becomes slow for single-query (non-batched) workloads. The authors suggest using an ANN index on the landmarks themselves to fix this.
- Cold Start/Maintenance: Building the synopsis requires a one-time cost of running many sample queries. Future work could explore adaptive sampling to reduce this labeling overhead as the underlying corpus changes.
Summary updated