how approximate kNN with HNSW computes vector similarity efficiently
Classic text search finds documents that contain the same words as the query. It does not recognize that a search for waterproof jacket should also match a product called weatherproof outdoor coat, even though not a single word overlaps. Vector search solves exactly this problem: text is represented as embeddings, points in a high dimensional space, and similar meaning translates into spatial closeness. The real challenge starts afterward, because finding the nearest neighbor across millions of vectors is expensive. Approximate kNN with the HNSW algorithm solves this scaling problem by trading a small accuracy loss for enormous speed gains. This article explains how HNSW works technically, where exact kNN still has its place, and how the two central levers, num_candidates and the similarity metric, are configured in practice.
Table of Contents
- 1. Where classic text search hits its limits on meaning similarity
- 2. From embeddings to vector space: how similarity is measured
- 3. Exact kNN versus approximate kNN: the fundamental trade-off
- 4. The HNSW algorithm: how graph navigation actually works
- 5. Practical configuration: index_options in the dense_vector mapping
- 6. The search request: the knn query block with k and num_candidates
- 7. num_candidates tuning: the recall versus latency trade-off
- 8. Hybrid filtering: combining kNN with classic filters
- 9. Limits and monitoring: measuring recall, index size, rebuild cost
- 10. Summary
- 11. FAQ
1. Where classic text search hits its limits on meaning similarity
BM25-based text search ranks documents by how often and how rarely the search terms appear in the document and across the whole index. That works well as long as customers use the same terms as the product catalog. As soon as a synonym, a paraphrase, or a different formulation comes into play, for example a search for quiet kitchen mixer instead of low noise stand mixer, plain text search simply returns no results, even though the exact right product exists in the catalog.
Synonym lists can close part of that gap but scale poorly, since every new formulation has to be maintained by hand. Vector search takes a fundamentally different approach: an embedding model turns text into a numeric vector that encodes the meaning of that text in space. Two texts with similar meaning produce vectors that sit close together in that high dimensional space, regardless of which specific words were used.
2. From embeddings to vector space: how similarity is measured
An embedding model typically maps text onto a vector with several hundred to several thousand dimensions, commonly 384, 768, or 1536 values per vector. Elasticsearch stores such vectors in the dense_vector field type and offers several similarity metrics for computing distance or similarity between two vectors: cosine measures the angle between two vectors regardless of their length, dot_product is computationally cheaper and suits normalized vectors, and l2_norm measures the euclidean distance.
The choice of metric depends on the embedding model in use: most modern sentence transformer models are trained for cosine similarity and deliver the most reliable results with it, while some models are explicitly optimized for dot_product to save compute time. The similarity metric is set directly in the field mapping and cannot be changed afterward without rebuilding the index.
PUT products
{
"mappings": {
"properties": {
"description_embedding": {
"type": "dense_vector",
"dims": 768,
"index": true,
"similarity": "cosine"
}
}
}
}
3. Exact kNN versus approximate kNN: the fundamental trade-off
Exact kNN, implemented in Elasticsearch through a script_score query with a vector distance function, compares the query against every single vector in the index and guarantees the actually nearest neighbors. Compute cost grows linearly with the number of documents, which is trivial for a few thousand candidates in milliseconds, but quickly costs several seconds per query at several million vectors, making it unusable for a live search on a storefront.
Approximate kNN gives up the guarantee of exact results in exchange for speed. Instead of checking every vector, the algorithm navigates through a graph structure built ahead of time and finds the actually nearest neighbors with high, but not absolute, probability. For most product search use cases that small accuracy loss is entirely acceptable, since a single perfectly matching result rarely exists anyway, only a set of similarly good matches.
4. The HNSW algorithm: how graph navigation actually works
HNSW stands for Hierarchical Navigable Small World and builds a multi layer graph during indexing, where every vector is a node and edges connect to its nearest neighbors. The top layer contains only a few nodes with long range connections, while lower layers grow progressively denser until the bottom layer contains every vector. A search starts on the thin top layer, jumps roughly toward the target region, and descends layer by layer, getting more precise at each level.
This principle resembles a map with several zoom levels: you start with a coarse overview map to find the right region, then switch to increasingly detailed maps to pin down the exact location. Because every layer only needs a handful of hops to reach the target region, search time grows logarithmically with the number of vectors, not linearly as with exact kNN. That is the actual reason HNSW still delivers single digit millisecond response times even at tens of millions of vectors.
5. Practical configuration: index_options in the dense_vector mapping
The structure of the HNSW graph is controlled through index_options when the mapping is created. The m parameter sets how many edges each node keeps to its neighbors at most, a higher value improves search quality but increases memory usage and indexing time. The ef_construction parameter determines how thoroughly the graph search looks for the best neighbors while building the graph, and affects only indexing speed and later search quality, not search speed itself.
For most product catalogs Elasticsearch's default values are a solid starting point, and tuning only pays off once concrete recall measurements show that too many relevant results are being missed. Any change to graph parameters should always go hand in hand with a full reindex, since existing graph structures cannot be densified after the fact.
PUT products
{
"mappings": {
"properties": {
"description_embedding": {
"type": "dense_vector",
"dims": 768,
"index": true,
"similarity": "cosine",
"index_options": {
"type": "hnsw",
"m": 16,
"ef_construction": 100
}
}
}
}
}
6. The search request: the knn query block with k and num_candidates
A kNN query in Elasticsearch consists of the query vector, the k parameter, which specifies how many results are ultimately wanted, and the num_candidates parameter, which determines how many candidates per shard are considered during graph navigation before the best k of them are returned. This two stage construction is the key to making approximate kNN controllable in practice.
A higher num_candidates value means the algorithm checks more potential neighbors before making its final selection, which raises the probability of actually finding the nearest neighbors, but also costs more compute time. Elasticsearch recommends, as a rule of thumb, choosing num_candidates at least two to three times as large as k, though the optimal factor can differ significantly depending on the dataset and accuracy requirements.
GET products/_search
{
"knn": {
"field": "description_embedding",
"query_vector": [0.021, -0.153, 0.402, "..."],
"k": 10,
"num_candidates": 100
},
"_source": ["sku", "name", "price"]
}
7. num_candidates tuning: the recall versus latency trade-off
In practice an iterative approach to tuning num_candidates works best: start with a conservative value, measure response time under realistic load, and spot check the returned results against an exact kNN reference search on a subset of the data to determine actual recall. Recall here means the share of the truly nearest neighbors that the approximate search actually found.
For very large product catalogs with several million entries, it is worth choosing num_candidates differently depending on the use case rather than globally: an interactive storefront live search usually cares more about low latency than about perfect recall, while a batch process, for example suggesting similar products for cross selling, can afford higher recall at somewhat longer compute time.
8. Hybrid filtering: combining kNN with classic filters
In a real storefront, a semantic search almost never runs across the entire catalog, but within a category, a price range, or subject to availability. Elasticsearch supports this through a filter parameter directly inside the knn block, applied before graph navigation. This so called pre-filtering ensures that the HNSW search only looks for neighbors within the filtered subset, instead of searching globally first and filtering afterward.
The difference is substantial with strongly restrictive filters: without pre-filtering, a global search could theoretically return all k results only to have them entirely discarded by the filter afterward, leaving too few or no results at all. With pre-filtering, the graph navigates specifically through the relevant subset, which means more compute effort within that subset for highly selective filters, but reliably delivers complete result sets.
GET products/_search
{
"knn": {
"field": "description_embedding",
"query_vector": [0.021, -0.153, 0.402, "..."],
"k": 10,
"num_candidates": 100,
"filter": {
"bool": {
"filter": [
{ "term": { "category_id": 42 } },
{ "range": { "price": { "lte": 150 } } }
]
}
}
}
}
9. Limits and monitoring: measuring recall, index size, rebuild cost
The HNSW graph sits fully in memory in addition to the actual vectors, which means significant memory overhead per node for large catalogs with high dimensional embeddings. Before going to production it is worth realistically estimating how much additional heap and off heap memory the graph will require, especially when multiple vector fields per document or multiple languages are indexed in parallel.
Since index_options cannot be changed after the fact without a full rebuild of the affected index, any change to graph parameters should first be validated on a test index with a representative subset of the product data. Regular monitoring that draws recall spot checks against an exact reference search and observes the actual response time distribution under production load prevents search quality from silently degrading as the catalog grows and relative accuracy tends to drop with an unchanged num_candidates.
| Criterion | Exact kNN (script_score) | Approximate kNN (HNSW) | Practical relevance |
|---|---|---|---|
| Compute complexity | Linear to all documents | Logarithmic via graph navigation | Approximate scales to millions of vectors |
| Response time at 1M vectors | Several seconds | A few milliseconds | HNSW is practical for live search |
| Accuracy | Always exact | Approximation, depends on num_candidates | Recall can be tuned deliberately |
| Memory footprint | No additional index needed | Additional HNSW graph in memory | Trade-off memory against speed |
| Best fit | Small candidate sets, reranking | Large catalogs, interactive live search | Combining both approaches is often sensible |
Mironsoft
Search index setup, relevance tuning, and Magento search
Magento search that shows the wrong products first?
We set up Elasticsearch or OpenSearch for Magento cleanly, tune relevance and facets to the actual catalog, and optimize indexing processes for large catalogs.
Relevance Tuning
Match search results and facets to actual customer needs.
Search Migration
Guide a clean migration from Solr or MySQL search to Elasticsearch/OpenSearch.
Index Performance
Make indexing processes for large catalogs reliable and performant.
10. Summary
kNN Search for Semantic Similarity: The Essentials at a Glance
Core principle
Embeddings encode meaning as points in vector space, kNN finds the nearest neighbors of a query vector regardless of exact word overlap.
HNSW scaling
The multi layer graph navigates from coarse to fine and makes search time logarithmic instead of linear, which is why millions of vectors can be searched in milliseconds.
Key lever
num_candidates controls the trade-off between recall and latency and should be calibrated iteratively against an exact reference search.
Practical tip
Pre-filtering inside the knn block prevents empty result sets when filters like category or price range are highly restrictive.