🤖 AI / ML

Approximate Nearest Neighbor Search

ANN · HNSW · FAISS · Approximate k-NN

Definition

Approximate nearest neighbor search is a family of algorithms that find vectors close to a query with a controllable trade-off between accuracy and speed, using specialised index structures.

Why approximate search exists

Modern recommenders and semantic search rest on vector embeddings: every product and every shopper
is a point in a high-dimensional space. The task is to find the points nearest to a query.

Exact search — scanning every vector — is too slow on large catalogues:

Catalogue: 5,000,000 products
Embedding dimensionality: 128
Exact search: ~640 million operations per query → 500–2,000 ms

ANN (HNSW): under 5 ms at recall above 95%

ANN solves this by building index structures that discard most irrelevant vectors without ever
examining them.

The main algorithms

Algorithm	Principle	Strength
HNSW	Hierarchical graph	High accuracy, dynamic inserts
IVF (inverted file)	Clustering plus in-cluster search	Memory efficiency on large datasets
LSH	Hashing by random projections	Simplicity, no GPU needed
ScaNN	Anisotropic quantisation	High speed, tuned for search

FAISS is the most widely used library, supporting several algorithms and GPU acceleration.

Applications in e-commerce

Similar items. A product page needs 10–20 visually or semantically similar items in
milliseconds. An ANN index over product embeddings answers in real time.

Semantic search. A query such as a warm coat for autumn becomes an embedding, ANN searches the
product vectors, and relevant results come back with no exact word match.

Personalized recommendations. A two-tower model produces a user vector and item vectors. ANN
finds the items nearest to the user vector in O(log n) instead of O(n).

The accuracy–speed trade-off

ANN is tuned through index parameters. In HNSW the key ones are:

ef_construction — accuracy during index construction, which drives indexing time
ef_search — accuracy during search, which drives latency

Raising them improves recall and slows search. In production the balance is usually set so that
recall at 10 stays at or above 95% with latency under 10 ms.

Important: when the catalogue changes, HNSW accepts incremental inserts. IVF indexes often
require a full rebuild — worth weighing when the catalogue updates frequently.

Frequently asked questions

Why is exact k-NN unsuitable for production?

Exact k-NN computes the distance from the query to every vector in the database. At 10 million product embeddings of 128 dimensions that is roughly 1.3 billion operations per query — far too slow for real time. ANN gives up a small share of accuracy, usually under 5%, and cuts query time by a factor of 100 to 1,000.

What is HNSW and why is it the default?

HNSW builds a multi-layer graph where search starts on a coarse top layer and refines downward. It delivers high recall at low latency and handles dynamic data well — new vectors can be added without rebuilding the index. It is implemented in FAISS, hnswlib, Weaviate and Qdrant.

What recall is typical in recommendations?

Recall at k above 95% with well-tuned index parameters. Losing 5% of accuracy makes almost no practical difference to recommendation quality — nobody notices the difference between the tenth and the eleventh similar item.