Service Level Objective (SLO) for Recall

Recall is the primary accuracy metric for a vector similarity search. It measures the proportion of true nearest neighbors (from the ground truth set) that are successfully retrieved by the approximate nearest neighbor (ANN) index.

• Formula: Recall = (Number of Retrieved True Neighbors) / (Total True Neighbors in Ground Truth).
• Example: For a k=10 search, if the system returns 8 of the actual 10 closest vectors, the recall is 80% (0.8).
• Ground Truth is established by an exact, brute-force k-NN search, which is computationally expensive but provides the benchmark for the faster, approximate index.

The Service Level Indicator (SLI) is the specific, measured value of recall over a defined window. It is the raw metric from which SLO compliance is calculated.

• Measurement: Typically computed as a ratio of successful queries (those meeting a recall threshold) to total queries over a time period (e.g., 28 days).
• Example SLI Measurement: (Queries with recall >= 0.95) / (Total Queries).
• Probing: Often measured via a synthetic canary query pipeline that runs periodic exact and approximate searches on a known dataset to compute the live recall SLI without relying on user traffic.

The SLO target is the minimum acceptable value for the SLI, expressed as a percentage or decimal. The compliance window is the rolling time period over which adherence to the target is evaluated.

• Typical Target: "95% of queries shall have a recall of at least 0.98 over a rolling 28-day window."
• Window Choice: A 28-day (or 30-day) window is common, smoothing over daily and weekly traffic patterns and providing a stable measurement period.
• Burn Rate: Tracks how quickly the error budget is being consumed. A fast burn rate triggers urgent alerts, while a slow burn rate allows for planned, riskier changes.

The error budget quantifies the acceptable unreliability. It is 1 - SLO. This budget dictates the pace of innovation and change management.

• Calculation: For a 99.9% recall SLO, the error budget is 0.1%. Over a 28-day window, this allows for ~40 minutes of "unreliable" search time.
• Usage: Engineering teams can "spend" the budget on deploying risky index changes, experimenting with new algorithms, or performing major maintenance. If the budget is exhausted, all non-essential changes are halted to focus on stability.
• Policy Driver: It transforms SLOs from a passive target into an active resource management tool.

Recall is directly governed by the parameters of the Approximate Nearest Neighbor (ANN) index. Tuning these involves a fundamental trade-off with latency and resource cost.

• Key Parameters:
  • efConstruction / M (HNSW): Controls index connectivity and density. Higher values increase recall but slow down build time and memory usage.
  • nlist / nprobe (IVF): Number of cells and cells to probe. Increasing nprobe improves recall at the cost of query latency.
  • quantization (PQ, SQ): The level of compression for vectors. Coarser quantization reduces memory/disk footprint but can lower recall.
• Tuning Process: These parameters are set during index creation and rebuilds, establishing the upper bound for achievable recall.

At query execution, runtime parameters adjust the trade-off between recall, latency, and throughput. System state can also cause recall to degrade.

• Runtime Parameters:
  • efSearch (HNSW): Size of the dynamic candidate list. Increasing it boosts recall but increases latency.
  • k (Search Depth): Returning more neighbors (k) than requested can improve recall-at-N metrics.
• Degradation Triggers:
  • Index Corruption: Silent data corruption in vector files.
  • Configuration Drift: Unintended changes to query parameters.
  • Data Distribution Shift: New embedding models producing vectors outside the index's trained distribution.
  • High Load: Triggering load shedding or cache thrashing.

The core metric for a vector database's search accuracy. Recall is formally defined as the proportion of true nearest neighbors (from the complete dataset) that are successfully returned in the top-k results of a similarity search query.

• Calculation: Recall = (Number of relevant vectors retrieved) / (Total number of relevant vectors in the dataset).
• A recall of 1.0 (or 100%) means the search returned all true nearest neighbors, which is often computationally prohibitive at scale.
• In production, SLOs define a target recall (e.g., 0.95 over a 30-day window), balancing accuracy with latency and cost.

The complementary metric to recall, measuring the relevance of returned results. Precision is the proportion of retrieved vectors that are actually relevant to the query.

• Calculation: Precision = (Number of relevant vectors retrieved) / (Total number of vectors retrieved).
• High recall with low precision means returning many true neighbors but also many irrelevant ones, increasing post-filtering workload.
• Recall-Precision Trade-off: Tuning Approximate Nearest Neighbor (ANN) indexes often involves balancing these two metrics. An SLO for recall must be set with an understanding of its impact on precision.

The operationalization of an SLO. An Error Budget quantifies the acceptable amount of unreliability—or missed recall targets—over a compliance period.

• Derivation: If the SLO for recall is 95%, the error budget is 5% unreliability.
• Usage: It dictates the pace of innovation. Engineering teams can "spend" the budget on deploying risky changes (e.g., index algorithm updates). If the budget is exhausted, a freeze on changes is typically enforced to focus on stability.
• This creates a data-driven framework for balancing velocity and reliability.

The specific, measured metric that feeds into an SLO. For recall, the SLI is the actual, measured recall value over a defined window.

• Example SLI Measurement: "The 30-day rolling average of recall at k=100 for product search queries."
• Implementation: Requires a ground truth dataset or a sampling mechanism to periodically calculate the true recall of production searches against the full dataset.
• The SLI is the raw measurement; the SLO is the target value for that measurement.

The algorithmic foundation that makes large-scale vector search feasible but introduces the recall trade-off. ANN algorithms (e.g., HNSW, IVF) find similar vectors in sub-linear time by searching a pruned graph or partitioned space, sacrificing perfect recall for speed.

• Direct Impact on SLOs: The choice of ANN algorithm and its configuration parameters (e.g., ef_search for HNSW, nprobe for IVF) is the primary lever for controlling recall performance.
• The SLO for recall defines the minimum acceptable accuracy for these approximations in a production setting.

A key risk that SLOs for recall are designed to monitor. Index Degradation refers to the gradual decline in search accuracy (recall) of a vector index over time without the underlying data changing.

• Causes: Can include software bugs, corruption of in-memory graph structures (e.g., in HNSW), or fragmentation from excessive updates/deletions.
• Mitigation: SLO monitoring provides the alerting mechanism. Corrective actions may include index rebuilds or switching to a replica with a healthy index.
• This makes recall SLOs critical for proactive data quality, not just performance monitoring.