ANN Recall Trade-off

Controls the greedy search breadth during graph construction. A higher value builds a more connected, higher-quality graph, directly improving recall potential.

• Higher value: Increases index build time and memory usage but enables higher recall at query time.
• Lower value: Faster build times but creates a sparser graph with lower maximum achievable recall.
• Mechanism: Expands the dynamic candidate list during neighbor selection.

The primary query-time accuracy knob. It defines the size of the dynamic candidate list during the greedy search traversal.

• Higher value: Increases search latency linearly but improves recall by exploring more graph paths.
• Lower value: Faster search speed at the cost of missing true nearest neighbors.
• Distinction: Unlike efConstruction, this parameter is set at query time and can be dynamically adjusted per request without rebuilding the index.

Controls the number of inverted file clusters to search. In IVF-based indexes, the vector space is partitioned into Voronoi cells; nprobe specifies how many of the nearest centroids are visited.

• Higher value: Searches more partitions, increasing recall but also linearly increasing computational cost.
• Lower value: Restricts the search to fewer cells, trading accuracy for speed.
• Interaction: Often used with Product Quantization (PQ) to balance memory compression against search precision.

Defines the maximum number of outgoing connections per node in each layer of the HNSW graph.

• Higher M: Creates a denser graph with more express routes, improving recall at the cost of significantly higher memory usage and slower construction.
• Lower M: Reduces the index footprint but limits the navigable small-world properties, capping maximum recall.
• Standard: A value between 16 and 64 is common, with 32 often providing a strong balance between memory and accuracy.

In Google's ScaNN algorithm, this parameter directly constrains the number of distance computations allowed per query.

• Mechanism: ScaNN uses anisotropic vector quantization to score vectors; the search budget caps the total number of dot-product operations.
• Tuning: A higher budget allows the algorithm to score more candidates, increasing recall. This provides a deterministic, hardware-aware way to enforce a strict latency budget.
• Use Case: Critical for achieving sub-millisecond P99 latency on billion-scale datasets.

The business requirement that drives all parameter tuning. It defines the acceptable proportion of true nearest neighbors that must appear in the top K results.

• Recall@1: Measures if the single absolute nearest neighbor was retrieved. Critical for exact match lookups.
• Recall@100: Measures retrieval completeness for downstream re-ranking stages.
• Trade-off: Moving from 95% to 99% Recall@10 often requires a non-linear, 2-5x increase in search latency.

The primary metric for quantifying the accuracy side of the trade-off. Recall@K measures the proportion of true nearest neighbors found within the top K results returned by an ANN algorithm.

• K=10: Measures if the true top-10 neighbors appear in the returned top-10
• Recall@1: Strictest measure—did the single closest vector get returned?
• A system with 0.95 Recall@10 sacrifices 5% accuracy for potentially orders of magnitude faster search
• Critical for tuning: raising recall targets increases latency and memory consumption

The Hierarchical Navigable Small World algorithm exposes three primary knobs that directly control the recall-speed trade-off:

• M (out-degree): Number of connections per node. Higher M increases recall but consumes more memory and slows insertion
• efConstruction: Search depth during index building. Higher values build a more accurate graph at the cost of longer build times
• efSearch: Search depth during query time. The most dynamic trade-off lever—increasing efSearch improves recall linearly while increasing latency
• Doubling efSearch typically adds 10-20% latency for 1-5% recall improvement

Product Quantization (PQ) applies lossy compression to vectors, trading recall for dramatic memory reduction. The trade-off is controlled by the number of sub-vector segments.

• Decomposes a 768-dim vector into M sub-vectors (e.g., 96 segments of 8 dimensions)
• Each sub-vector is quantized to the nearest centroid from a codebook
• Fewer segments (lower M): Higher compression, lower memory, worse recall
• More segments (higher M): Less compression, higher memory, better recall
• Enables billion-scale search in RAM-constrained environments where exact search is impossible

DiskANN shifts the trade-off boundary by moving the vector index from expensive RAM to commodity SSDs, accepting higher latency for radically lower cost at scale.

• Builds a graph index on SSD with minimal in-memory caching of frequently accessed nodes
• Achieves 95%+ Recall@10 with sub-10ms latency on billion-scale datasets
• Trade-off: 3-10x slower than pure in-memory HNSW but 10-20x cheaper per query
• Ideal for cost-sensitive applications where P99 latency can tolerate 10-50ms instead of 1-5ms

Horizontal index sharding partitions a large vector index across multiple nodes, trading coordination overhead for parallel throughput. The recall trade-off manifests in merge strategies.

• Each shard searches its partition independently and returns top-K candidates
• A merge node combines results, potentially missing neighbors that span shard boundaries
• Replication factor: Duplicating shards increases recall by providing redundant search paths
• Trade-off: higher replication improves recall but multiplies storage cost and synchronization complexity

The exact k-nearest neighbors search represents the upper bound of recall (1.0) and the lower bound of speed. Understanding this baseline is essential for calibrating acceptable trade-offs.

• Brute-force computes cosine similarity against every vector in the index
• O(N * D) complexity where N is index size and D is dimensionality
• For 1M vectors at 768 dimensions: ~50-100ms per query on modern hardware
• ANN algorithms achieve 0.5-5ms at 0.95 recall—a 20-200x speedup for a 5% accuracy loss
• The trade-off is not linear: small recall sacrifices yield exponential speed gains