3. Search Indexes: Exact vs Approximate

Overview

Here you compare the main types of indexes for vector search: exact (they guarantee finding the true top-K but are slow) vs approximate (fast but they can miss some results). You'll understand the fundamental trade-off of vector databases.

---

Classifying indexes

Exact indexes:

• Brute force: Check every vector
• KD-Tree: A space-partitioning tree (does NOT work well in high dimensions)
• Ball Tree: A KD-Tree variant (it doesn't scale well either)

The problem: They all suffer from the "curse of dimensionality" → slow in 1536D.

---

Approximate indexes (ANN - Approximate Nearest Neighbors):

• HNSW: A hierarchical navigable graph ⭐ (the most used)
• IVF: Clustering + searching within clusters
• LSH: Locality-Sensitive Hashing
• ScaNN: Google's optimized ANN (an advanced variant)
• ANNOY: Spotify's ANN (random trees)

The advantage: They scale to millions/billions of vectors.

---

Comparison: Exact vs Approximate

Aspect	Exact (brute force)	Approximate (HNSW/IVF)
Precision	100% ✅	~95-99% ⚠️
Speed	O(N) - Slow ❌	O(log N) - Fast ✅
Memory	Low (just the vectors)	Medium-High (an extra index)
Scalability	Up to ~100K ⚠️	Millions/billions ✅
Build time	None	Minutes-hours (once)
Typical use	Small datasets	Production (millions of vectors)

---

When to use each one?

Use exact search when:

• The dataset is < 100,000 vectors
• Latency isn't critical (> 500ms is acceptable)
• You need a 100% guarantee of the correct top-K

Example: Searching a personal library (10K documents).

---

Use approximate search when:

• The dataset is > 100,000 vectors
• Latency is critical (< 100ms required)
• 95-99% precision is enough (it almost always is)

Example: Semantic search in production (millions of documents).

---

Precision vs speed parameters

Approximate indexes let you tune the trade-off:

HNSW:

ef_search = 50  → Fast, ~95% precision
ef_search = 200 → Slow, ~99% precision

IVF:

nprobe = 1   → Very fast, ~90% precision
nprobe = 10  → Fast, ~95% precision
nprobe = 100 → Slow, ~99% precision

The principle: More searching → more precision → more time.

---

Visualizing the trade-off

Precision
   ↑
100%|    • Brute force
    |
 99%|         • HNSW (ef=200)
    |
 95%|              • HNSW (ef=50)
    |                   • IVF (nprobe=10)
 90%|                        • LSH
    |
    └─────────────────────────────→ Speed
      Slow                    Fast

The typical sweet spot: ~98% precision at 1000x the speed of brute force.

---

Building the index

Brute force: Needs no build step (you just store the vectors).

Approximate indexes: They require a "build" step (build time):

1. Take all the vectors in the dataset
2. Build the data structure (graph, clusters, hashes)
3. Save the index to disk/memory

Time: Minutes-hours depending on the size
Frequency: Once (or when you add many new vectors)

Important: Build time is an upfront investment. Afterward, the queries are very fast.

---

Indexes in vector databases

Pinecone:

• Uses HNSW by default
• Automatic configuration (you don't tune the parameters by hand)

Weaviate:

• HNSW by default
• The option to configure ef_construction, ef_search

Qdrant:

• Optimized HNSW
• Fine-grained control over the parameters

FAISS (Facebook):

• Multiple indexes (IVF, HNSW, PQ, etc.)
• Requires manual configuration

Milvus:

• Support for HNSW, IVF, ANNOY, ScaNN
• Configurable based on the use case

---

Summary

Key points:

• Exact: 100% precision, doesn't scale (< 100K vectors)
• Approximate: 95-99% precision, scales to millions ✅
• A tunable trade-off: Precision vs speed (the parameters)
• In production: Almost always approximate (HNSW or IVF)
• Build time: An upfront investment, with very fast queries afterward

---

Next capsule: 04-hnsw-and-graphs.md — How HNSW works (the most used index).