Approximate vs Exact Search

In the previous lesson, we introduced the concept of finding "Neighbors." We touched on a painful reality: Exact Search (calculating distance to everyone) does not scale.

In production AI engineering, we almost always opt for Approximate Nearest Neighbor (ANN) search. This introduces a tension that every engineer must manage: The Speed-Accuracy Trade-off.

In this lesson, we will look at exactly what "Approximate" means, what "Recall" is, and why a 2% loss in accuracy is a price worth paying for a 1000x increase in speed.

---

1. What is Exact Search? (Brute Force)

Exact search (or Flat search) is the benchmark. It calculates the similarity between the query vector and every single vector in the index.

Pros:

• Perfect Recall: You are guaranteed to find the absolute best matches.
• Simplicity: No complex data structures or re-indexing required.

Cons:

• O(n) Latency: The search time increases linearly with your data.
• Unusable at Scale: Beyond 100k vectors, it becomes too slow for user-facing applications.

graph TD
    A[Query] --> B[Row 1]
    A --> C[Row 2]
    A --> D[Row 3]
    A --> E[Row 1,000,000]
    subgraph Exhaustive_Calculation
    B & C & D & E
    end

---

2. What is Approximate Search (ANN)?

ANN search doesn't check every row. Instead, it uses a Vector Index to jump directly to the most likely neighborhood of the query.

Imagine you are looking for a house in a city.

• Exact Search: You walk into every single house in the city and measure how much you like it.
• Approximate Search: you use a Map. You go to the "Green Neighborhood" and check the 5 houses there. You might miss a house in the "Blue Neighborhood" that was slightly better, but you saved weeks of time.

The Mechanism: Space Partitioning

ANN algorithms work by "partitioning" the vector space. They group similar vectors together during the Indexing Phase so that the Search Phase only has to look at a tiny fraction of the data.

---

3. Measuring the "Cost" of Speed (The Recall Metric)

If we aren't being 100% accurate, how do we know our search is "good"? We use a metric called Recall.

Recall @ K: The percentage of the "true" top-k results (found by exact search) that are included in the results returned by your approximate search.

Example:

• You ask for the top 10 neighbors using Exact Search.
• You ask for the top 10 neighbors using ANN.
• If the ANN result contains 9 of the same items as the Exact result, your Recall @ 10 is 0.9 (90%).

In production RAG systems, a Recall of 0.90 to 0.95 is usually sufficient. Users rarely notice if the 3rd most similar document was swapped for the 4th, as long as the content is still relevant.

---

4. Why We Choose ANN for AI

1. The Human Perception Limit

In image search or recommendation systems, the difference between a 0.88 similarity score and a 0.87 similarity score is invisible to the human eye.

2. The LLM's Resilience

Large Language Models are excellent at filtering noise. If you retrieve 5 documents via ANN, and one of them is slightly "off," the LLM will usually ignore the irrelevant one and focus on the high-quality ones. The cost of retrieving 100% perfect matches usually exceeds the benefit.

3. The Infrastructure Budget

Keeping a 10M vector index in RAM for Exact Search requires massive, expensive servers. ANN algorithms allow us to use Quantization and Compressed Indexes, allowing us to run the same search on much cheaper hardware.

---

5. Python Comparison: Flat vs. ANN Indexing (Conceptual)

Let's look at how we might simulate the performance difference. Note: To run this properly, you would use a library like Faiss or Hnswlib.

import time
import numpy as np

# 1M documents, 128 dimensions (smaller for speed of demo)
N = 1000000
D = 128
X = np.random.random((N, D)).astype('float32')
query = np.random.random((1, D)).astype('float32')

# --- Simulation 1: EXACT SEARCH ---
start = time.time()
# Calculate distance to ALL 1M rows
distances = np.linalg.norm(X - query, axis=1)
top_k_exact = np.argsort(distances)[:10]
exact_time = time.time() - start

# --- Simulation 2: APPROXIMATE SEARCH (Conceptual) ---
# In reality, this would use a pre-built index
# We simulate it by checking only 1% of the data
start = time.time()
subset_indices = np.random.choice(N, 10000) # Check only 10,000 rows
subset_distances = np.linalg.norm(X[subset_indices] - query, axis=1)
top_k_ann = subset_indices[np.argsort(subset_distances)[:10]]
ann_time = time.time() - start

print(f"Exact Search Time: {exact_time:.4f}s")
print(f"Approx Search Time (Simulated): {ann_time:.4f}s")
print(f"Speedup: {exact_time / ann_time:.1f}x")

---

6. When Should You Use Exact Search?

Despite the power of ANN, there are three scenarios where Exact Search (Flat Index) is actually better:

1. Small Datasets: If you have fewer than 10,000 vectors, the overhead of building an ANN index (which takes time and memory) isn't worth it. Exact search will be faster than 10ms anyway.
2. Frequency of Update: ANN indexes (like HNSW) are often slow to update. If your data is changing every second (e.g., real-time stock sentiments), a Flat index is much easier to maintain.
3. Requirement for 100% Precision: In specific scientific or legal auditing tasks where "nearly right" is a legal liability, Exact search is mandatory.

---

Summary and Key Takeaways

The choice between Exact and Approximate search is a business decision, not just a technical one.

1. Exact Search is for correctness and small scale.
2. Approximate Search (ANN) is for speed and massive scale.
3. Recall is the metric that tells you how much quality you are sacrificing for speed.
4. Production RAG almost exclusively uses ANN.

In the next lesson, we will dive into the specific Indexing Strategies—the "Maps" of the vector world—including HNSW (the industry favorite), IVF (the clustering legend), and PQ (the compression master).

---

Exercise: The Recall Assessment

You are running an ANN search and notice that your "Recall @ 10" has dropped to 0.70 (70%) after adding 5 million more documents to your index.

1. Why does adding more data often lower the recall of an approximate index?
2. What are two things you could do to fix this? (e.g., Increase search complexity, Re-build the index with more clusters).
3. If this were a "Movie Recommendation" app, would 70% recall be a problem? What if it were a "Medical Diagnosis" app?

Reflecting on the Context of Accuracy is what makes a senior engineer.