Vector Approximate Nearest Neighbor
Every vector search asks the same question: which stored vectors sit closest to my query? Checking every vector gives the perfect answer but costs too much time on large data. Approximate nearest neighbor search, shortened to ANN, finds results that are nearly perfect in a tiny fraction of the time.
Exact vs Approximate
Picture a teacher who must find the three tallest students in a school of 5,000 children. Measuring every child gives the exact answer. Asking each classroom to send its two tallest students and measuring only those gives an answer in minutes. The second method might miss one very tall child hiding in an unusual class, but it works far faster.
EXACT SEARCH (k-NN)
Compare the query with all 10,000,000 vectors
Result: perfect, slow
APPROXIMATE SEARCH (ANN)
Compare the query with about 5,000 promising vectors
Result: almost perfect, very fast
Why Exact Search Does Not Scale
Distance calculations on high-dimensional vectors are expensive. A search over 100 million vectors with 768 dimensions requires billions of multiplications for a single query. Dozens of users searching at once multiply that cost. No ordinary server keeps up.
The Core Trade-Off
ANN gives up a small amount of accuracy to gain large speed. You control the balance with index settings.
QUALITY vs SPEED
Recall
100% | * exact search (slow)
98% | *
95% | *
90% | *
80% | * (very fast)
+----------------------------------- Speed
Recall: The Quality Score
Recall measures how many of the true nearest neighbors the approximate search finds.
True top 10 neighbors (from exact search): A B C D E F G H I J
ANN returned top 10: A B C D E F G H K L
Found 8 of the 10 true neighbors
Recall@10 = 8 / 10 = 80%
Most production systems target recall between 90 and 99 percent. Users rarely notice the missing results because the returned items are still highly relevant.
How ANN Algorithms Save Time
| Family | Idea | Example |
|---|---|---|
| Graph-based | Walk through a network of linked neighbors toward the query | HNSW |
| Cluster-based | Group similar vectors and search only the closest groups | IVF |
| Compression-based | Shrink vectors so comparisons run faster | Product quantization |
| Hash-based | Assign similar vectors to the same bucket | Locality-sensitive hashing |
| Tree-based | Split space repeatedly into smaller regions | Random projection trees |
The Shortcut Principle
ALL ANN METHODS FOLLOW ONE PATTERN
Millions of vectors
|
v
Smart structure narrows the field
|
v
A few thousand candidates
|
v
Exact distance check on candidates only
|
v
Top K results
Knobs You Can Turn
- Search width: Examine more candidates for higher recall and slower queries.
- Index quality: Spend more build time for a better structure.
- Compression level: Store smaller vectors for lower memory and slightly lower recall.
Measuring Your Own Trade-Off
- Pick 100 to 500 sample queries from real usage.
- Run them against a flat index to collect the true neighbors.
- Run the same queries against your ANN index.
- Calculate recall and record the average response time.
- Change one setting at a time and repeat the test.
When Exact Search Still Makes Sense
Small collections under roughly 100,000 vectors often run exact search fast enough. Legal or scientific work that demands every true match also favors exact search. Use ANN when the data grows large or response time matters more than the last few percent of accuracy.
ANN powers nearly every modern vector database. Understand recall, speed, and memory as three connected dials, and you can tune any index with confidence.