ANN Recall vs Latency Tradeoffs

The Vector Database Trade-off Triangle

In relational SQL databases, indexing is exact: a B-Tree lookup returns $100%$ exact matches.

In high-dimensional Vector Search ($1536$-d vectors), exact brute-force search takes seconds per query ($O(N \cdot d)$ complexity).

Approximate Nearest Neighbor (ANN) algorithms trade exact recall accuracy to deliver sub-millisecond search speeds.

Every vector database engineer operates within the ANN Trade-off Triangle:

                              RECALL ACCURACY
                              (Search Precision %)
                                   ╱     ╲
                                  ╱       ╲
                                 ╱         ╲
  QUERY LATENCY (QPS) ◄─────────────────────────► RAM MEMORY FOOTPRINT
  (Sub-ms Throughput)                             (Hardware Cost $)

You can optimize any two corners of the triangle, but you must compromise on the third:

• High Recall + Low Latency: Requires huge RAM memory (HNSW graphs loaded in RAM).
• Low RAM + Low Latency: Requires lowering Recall expectations (Quantized Product Quantization).
• High Recall + Low RAM: Requires higher latency (Disk-based search like DiskANN).

Key Index Hyperparameters & Tuning Knobs

1. HNSW Index Parameters (Graph-Based)

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ PARAMETER                │ WHAT IT CONTROLS         │ TUNING IMPACT            │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ M                        │ Max bi-directional links  │ Higher M = Higher Recall,│
│                          │ per node in graph.       │ Higher RAM, Slower Build.│
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ ef_construction          │ Candidate queue size     │ Higher = Higher Graph    │
│                          │ during graph BUILD time. │ Quality, Slower Build.   │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ ef_search                │ Candidate queue size     │ Higher = HIGHER RECALL,  │
│                          │ during QUERY time.       │ HIGHER LATENCY (Lower QPS│
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

Tuning ef_search at Query Time

• Set ef_search = 16 $\to$ Latency $= 1.2\text{ ms}$, Recall $= 92%$. (High QPS throughput for web feeds).
• Set ef_search = 128 $\to$ Latency $= 8.5\text{ ms}$, Recall $= 99.4%$. (High precision for medical/legal RAG).

2. IVF Index Parameters (Clustering-Based)

• nlist: Number of Voronoi centroids created during indexing.
• nprobe: Number of centroid clusters searched per query.
  • Low nprobe = 1 $\to$ Super fast ($0.5\text{ ms}$), but low recall ($80%$).
  • High nprobe = 32 $\to$ Higher recall ($98%$), but slower latency ($12\text{ ms}$).

Memory Compression: Scalar vs Product Quantization

┌──────────────────────────┬──────────────────────────┬──────────────────────────┐
│ TECHNIQUE                │ COMPRESSION RATIO        │ RECALL IMPACT            │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Un-compressed FP32       │ 1x (4 Bytes / dimension) │ 100% Baseline Recall.    │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Scalar Quantization (SQ8)│ 4x RAM Reduction!        │ 98% - 99% Recall         │
│ (FP32 -> INT8)           │ (1 Byte / dimension)     │ (Minimal degradation).   │
├──────────────────────────┼──────────────────────────┼──────────────────────────┤
│ Product Quantization (PQ)│ 16x - 64x RAM Reduction! │ 90% - 95% Recall         │
│ (Vector Sub-spaces)      │ (Compact codebook bytes) │ (Best for Billions!).    │
└──────────────────────────┴──────────────────────────┴──────────────────────────┘

Say this out loud

ANN vector search operates on a 3 way trade off triangle between Search Recall, Query Latency, and RAM Index Memory. HNSW parameters M and ef construction govern graph quality during build time, while ef search tunes recall versus latency dynamically at query time. Scalar Quantization reduces vector RAM by 4x with minimal recall loss.

Followups to expect

1. What is DiskANN (Microsoft)? An ANN graph search algorithm designed to store compressed vectors and graph structures on fast NVMe SSD storage instead of RAM, enabling 1-billion-vector search on a single server node.
2. How does filtered vector search impact ANN recall? Applying strict metadata filters (category == 'Shoes') before vector search restricts the searchable HNSW graph, which can break graph connectivity and drop recall unless using filtered HNSW indexes (Qdrant).