PaperlayerView exact revision on arXiv

Source-linked AI summary

Analyzing and Reducing Search Quality Differences in Vector Similarity Search

Sara Mahdizadeh Shahri, Martin Prammer, Jignesh M. Patel, Akshitha Sriraman

arXiv:2608.25185v1cs.DBcs.OS

TL;DR

The paper addresses the gap between meeting a target mean recall and delivering consistent recall across individual queries in scalable approximate vector search. It introduces RCheck, which dynamically reallocates runtime search effort across query groups without modifying the index. In pgvector evaluations, RCheck improves recall-throughput trade-offs, including higher mean recall and more queries meeting target recall at matched throughput.

  • Problem

    Optimizing mean recall can conceal substantial query-level recall differences, leaving some queries below target while wasting computation on others above target.

  • Method

    RCheck measures recall per query group and dynamically increases search effort for groups below target while decreasing it for groups above target using existing runtime parameters.

  • Results

    At the same throughput, RCheck increases mean recall by up to 93% and enables up to 47% more queries to meet target recall than the globally tuned configuration.

  • Takeaways & Limitations

    Runtime search-effort reallocation can reduce recall differences while maintaining high throughput and avoiding expensive intrusive index changes.

  • Takeaways & Limitations

    RCheck assumes the target recall is achievable within the available performance budget; tuning cannot suffice when index quality or the budget makes the target unattainable.

Abstract

from arXiv · show

Modern database services scalably search over large data collections via Approximate Nearest Neighbor Search, which improves search performance at the cost of search quality, measured by recall. In practice, a database operator seeks to achieve a target mean recall while maximizing throughput across search queries. We show that optimizing for mean recall masks significant differences in recall across queries even when target recall is met. As a result, numerous queries face (1) below-target recall, hurting user experience and revenue and (2) above-target recall, wasting computation to deliver unnecessarily high search quality. Thus, it is critical to detect and reduce recall differences across queries. We design RCheck, a light-weight run-time system that identifies low-recall queries and reduces recall differences while achieving high throughput. RCheck's key design principle is to dynamically, efficiently adapt search effort by increasing effort for queries below target recall and decreasing effort for those above it. RCheck tunes available search effort parameters, making it readily deployable. We evaluate RCheck using the widely-used production-style pgvector database. At the same throughput, RCheck improves mean recall by 11-93% and enables 8-47% more queries to meet target recall compared to the state-of-the-art globally-tuned configuration.

1 Introduction

Vector similarity search uses approximate search to scale, but optimizing mean recall can conceal large query-level quality differences. RCheck addresses this by adapting search effort across query groups, improving recall-throughput trade-offs without intrusive index changes.

  • Motivation: Approximate nearest neighbor search scales vector retrieval by scanning only a subset of stored vectors, trading search quality for performance.Recall is the fraction of true nearest neighbors retrieved, with values closer to 1 indicating better quality.
  • Motivation: Optimizing target mean recall can mask substantial differences in recall across queries.In one example, overall mean recall is 0.87 against a 0.85 target despite a wide distribution.
  • Motivation: Queries in embedding-space group A average 0.21 recall, whereas group B averages 0.99 despite similar cluster sizes.The disparity persists across index configurations, index types, and embedding models.
  • Motivation: Uneven recall harms user experience and reliable service operation, with consequences including reduced engagement and revenue.These consequences motivate detecting and reducing recall differences across queries.
  • Problem: Uniform global search effort helps low-recall groups only by imposing unnecessary computation on groups already achieving satisfactory recall.Offline index modifications are expensive and disruptive to deploy in production.
  • RCheck: RCheck dynamically increases effort for groups below target recall and decreases it for groups above target recall.It measures recall per group, adapts search effort with runtime feedback, and tunes existing parameters without intrusive index changes.
  • Evaluation: At the same target recall, RCheck improves throughput by 7–41% versus the best globally tuned configuration; at the same throughput, mean recall improves by 11–93%.It also enables 8–47% more queries to meet the target recall.
  • Contributions: The paper characterizes recall differences across index types, configurations, and embedding models and evaluates RCheck as a lightweight runtime system.The evaluation reports a recall-performance trade-off closer to the ideal.

2 Background

Vector databases use approximate nearest neighbor indexes to make large-scale similarity search practical. Their tunable construction and runtime parameters determine the trade-off between search quality and throughput, while runtime effort is typically applied uniformly across queries.

  • Vector search: Vector databases store embedding vectors and retrieve stored vectors most similar to a query under a distance metric.Examples include pgvector, FAISS, Milvus, and Weaviate.
  • ANNS: Exact similarity search is computationally infeasible at modern scales, motivating approximate nearest neighbor search.ANNS searches only a subset of stored vectors to reduce latency and increase throughput while potentially missing true nearest neighbors.
  • Index types: HNSW uses a multilayer graph, whereas IVFFlat partitions vectors into clusters and searches nearby clusters.Both expose parameters governing the search-quality versus throughput trade-off.
  • Parameters: HNSW uses M and ef_construction during index building and ef_search at runtime; IVFFlat uses nlist during construction and nprobes at runtime.These parameters control graph connectivity, candidate selection, partitioning, and the number of searched partitions or vectors.
  • Parameters: Build-time parameters require index reconstruction to change, while runtime parameters can be adjusted dynamically but are typically configured globally.Uniform runtime configuration applies the same search effort to all queries.

3 Studying Recall Differences Across Queries to a Vector Database

Recall varies substantially across query groups even when mean recall meets its target, and this variation persists across embeddings, index types, and tuning strategies. Global adjustments can improve low-recall groups but impose throughput costs or unnecessary work on high-recall groups, motivating RCheck’s finer-grained approach.

  • Recall differences: 0.21 versus 0.99 mean recall shows that comparable query groups can differ sharply despite identical search configurations.The groups cover comparable portions of the dataset.
  • Offline tuning: Index-construction tuning does not eliminate recall differences and can reduce throughput when improving low-recall groups.For HNSW, differences remain at M=12 and M=56; IVFFlat shows differences at nlist=1000 and nlist=3000.
  • Run-time tuning: Global run-time search-effort tuning improves low-recall groups but performs unnecessary work for high-recall groups, reducing overall throughput.The same search-effort increase can produce different recall improvements across groups.
  • Motivation for RCheck: RCheck therefore selectively increases effort for low-recall groups and avoids unnecessary effort for groups already meeting the target.This finer-grained approach is intended to reduce recall differences without significantly hurting throughput.

4 RCheck

RCheck is a run-time, group-level adaptation system that monitors recall and performance, then redistributes search effort across embedding-space regions. It uses feedback and operator-defined budgets to prioritize groups with the largest recall deficits while preserving throughput and tail-latency constraints.

  • Design goals: RCheck detects groups whose recall diverges from the target and applies group-specific search adaptations.The system operates at run-time rather than requiring offline index or embedding changes.
  • Design goals: RCheck increases search effort for low-recall groups and reduces unnecessary work for groups whose recall exceeds the target.This balances recall across queried embedding-space regions.
  • Feedback loop: Accepted search-effort changes take effect immediately, after which the next monitoring interval measures their impact and informs subsequent adaptations.RCheck thus operates as a feedback-driven control loop.
  • Grouping: Groups provide a practical middle ground between costly per-query adaptation and coarse global configuration.Queries are grouped by embedding-space region using k-means clustering.
  • Monitoring: During fixed-length intervals, RCheck samples queries, performs parallel exact searches for ground truth, and records per-group recall, throughput, and tail latency.These observations support incremental adaptation at runtime.
  • Runtime adaptation: RCheck maintains empirical recall and performance tables that map search effort to recall, throughput, and latency.The tables are updated incrementally and can be initialized from historical per-group statistics.
  • Runtime adaptation: Groups are ranked by recall deficit or surplus, and adaptations are accepted only when they fit the operator-defined performance budget.Groups with the largest deficits receive effort first, while recall-surplus groups provide potential throughput savings.

5 Experimental Methodology

The evaluation integrates RCheck with pgvector and compares it against globally tuned pgvector and an ideal per-query adaptation system. It spans four application domains, two ANN index types, multiple search-effort settings, and three target-recall operating points.

  • Platform and configurations: RCheck is integrated into the ANN Benchmarking framework at the client layer without modifying pgvector or the database itself.The underlying system is pgvector, a vector similarity search extension for PostgreSQL 16.
  • Datasets: The evaluation uses GloVe, FairFace, CIFAR-100, and DBPedia datasets spanning text, face recognition, vision, and knowledge-graph domains.Each dataset uses a 90/10 train-test split, with training vectors indexed and test vectors used as queries.
  • Baselines: RCheck is evaluated against pgvector with both HNSW and IVFFlat indexes, sweeping their global search-effort parameters.The parameters are ef_search for HNSW and probes for IVFFlat.
  • Operating points: The RCheck sweep evaluates low-, medium-, and high-target-recall operating points representing high-throughput, balanced, and high-recall regimes.These operating points are labeled RC_L_RT, RC_M_RT, and RC_H_RT.
  • Baselines: The ideal adaptation baseline assigns each query the minimum search effort needed to reach the target recall.This baseline represents the best achievable throughput-recall trade-off but requires true nearest neighbors at run-time.

6 Evaluation

Across datasets and ANNS configurations, RCheck improves the QPS–recall trade-off and narrows per-query recall differences relative to pgvector. Its benefits include higher throughput, improved recall, more queries meeting target recall, and lower tail latency at matched operating points.

  • QPS–recall trade-off: 40.91% higher throughput at target recall 0.85 shows RCheck outperforming pgvector while moving closer to the ideal adaptation curve.At 400 QPS, recall increases from 0.73 to 0.81, a 10.96% gain.
  • Deployment: RCheck can report infeasible recall-throughput requirements instead of satisfying them through unavailable search effort.Operators specify target recall and a performance constraint; RCheck finds an allocation or reports failure when the trade-off curve cannot satisfy both.
  • Recall distribution: 81.11% higher throughput is achieved with comparable search quality at high recall on FairFace, despite slightly lower mean recall.RCheck’s high-effort configuration has 78.3% of queries meeting target versus pgvector’s 81.8%.
  • QPS–recall trade-off: 25.63% higher throughput at recall 0.85 and 30.36% recall improvement at 187 QPS demonstrate RCheck’s gains on FairFace with HNSW.RCheck closes 69.4% of the gap to the ideal system at 0.85 recall.
  • QPS–recall trade-off: 6.95% higher throughput at recall 0.8 and a 92.86% recall gain at 200 QPS show that RCheck extends beyond HNSW to CIFAR-100 with IVFFlat.At 200 QPS, mean recall rises from 0.42 to 0.81.
  • Sensitivity analysis: Moderate monitoring intervals and 50 groups provide the best balance between adaptation responsiveness, estimation stability, recall, and throughput.A 15-second interval outperforms 5- and 60-second alternatives, while 5 groups lose 10.71% throughput and 200 groups lose 35.48% versus 50 groups.

7 Discussion

RCheck adapts search effort at runtime under performance constraints, reallocating computation among query groups without changing the index. Its correction ability is bounded by whether the target recall is achievable within the available performance budget.

  • Run-time adaptation under performance constraints: RCheck assumes the target recall is achievable within the available performance budget; otherwise search-effort tuning cannot suffice.Persistent shortfall at maximum allowed effort triggers an operator alert requiring offline intervention or revised constraints.
  • Search effort reallocation: Search-effort reallocation couples groups: improving low-recall groups may require reducing effort for groups already exceeding target recall.The current design prioritizes groups by their recall difference magnitude from the target.

8 Related Work

Prior work addresses ANN efficiency and search-quality disparities through index adaptation, ranking or representation fairness, and recall-variability measurement. RCheck instead detects and reduces disparities during ANNS by adapting search effort across query groups at runtime.

  • Global parameter tuning: Global ANNS tuning commonly applies one search-effort parameter to all queries, ignoring per-query or per-region variation in search quality.RCheck differs by adapting search effort at finer granularity based on observed recall.
  • Adaptive index structures: Adaptive index methods address workload heterogeneity by changing data access or partition organization, whereas RCheck leaves the ANN index structure unchanged.The cited examples include SPANN’s query-aware disk reads and QUAKE’s adaptive partitioning.
  • Differences in search quality: Information-retrieval fairness work primarily targets ranked outputs or embedding representations rather than disparities arising within the ANNS process.RCheck operates on uneven recall across embedding-space regions with fixed embeddings and ranking functions.
  • Differences in search quality: RCheck extends recall-variability research by both measuring group differences and reducing them at runtime through adaptive search effort.Wang et al. are described as focusing on measurement, while RCheck focuses on detection and reduction.

9 Conclusion

The paper concludes that mean recall can conceal substantial query-level disparities, motivating RCheck’s lightweight runtime adaptation. Compared with globally tuned search, RCheck reduces recall differences and improves recall-related outcomes at the same throughput.

  • Conclusion: RCheck identifies low-recall queries and reduces recall differences while maintaining high throughput through tunable search-effort parameters.The use of available parameters makes the system readily deployable.
  • Conclusion: Up to 93% higher mean recall and 47% more queries meeting target recall are achieved versus the state-of-the-art globally tuned search configuration.These results are reported at the same throughput.
Loading 2608.25185v1…