Metraipolis › archive › dc_3aaffabdf4c3

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.41407
License (as archived)
CC0-1.0
Archived
2026-11-02T05:02:53.630Z
SHA-256 of the archived text
75e43733466bb4c597d57b1dc137b7e0c6944f8a725ab8db1f8f96432d70d6df
Stable URL of this page
https://metraipolis.com/documento/dc_3aaffabdf4c3

How to cite

Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search — arXiv:2610.41407 — arXiv (en), https://arxiv.org/abs/2610.41407 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3aaffabdf4c3 (Metraipolis archive dc_3aaffabdf4c3, sha256 75e43733466bb4c597d57b1dc137b7e0c6944f8a725ab8db1f8f96432d70d6df)
BibTeX
@misc{dc3aaffabdf4c3,
  title = {Fidelity Synopses: Pre-Execution Plan Selection for Approximate Vector Search — arXiv:2610.41407},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41407},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3aaffabdf4c3; sha256 75e43733466bb4c597d57b1dc137b7e0c6944f8a725ab8db1f8f96432d70d6df},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41407. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Vector search has become a database operator with many physical implementations: different index families, build-time and search-time parameters, and compressed or disk-resident variants. Each trades cost against fidelity, the fraction of a query's exact top-k 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.72x the static deployment, with a batched lookup of 21-32 microseconds per query. The saving persists against the best static choice among the same indexes, and within a single index at no extra memory.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.IR, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB) ; Information Retrieval (cs.IR).
Pagina del lavoro: https://arxiv.org/abs/2610.41407 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T04:48:58.171Z dalla pagina https://arxiv.org/list/cs.IR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).