k-nearest neighbor (kNN) search

A k-nearest neighbor (kNN) search finds the k nearest vectors to a query vector, as measured by a similarity metric.

Common use cases for kNN include:

Elasticsearch supports two methods for kNN search:

In most cases, you’ll want to use approximate kNN. Approximate kNN offers lower latency at the cost of slower indexing and imperfect accuracy.

Exact, brute-force kNN guarantees accurate results but doesn’t scale well with large datasets. With this approach, a script_score query must scan each matching document to compute the vector function, which can result in slow search speeds. However, you can improve latency by using a query to limit the number of matching documents passed to the function. If you filter your data to a small subset of documents, you can get good search performance using this approach.

To run an approximate kNN search, use the knn option to search one or more dense_vector fields with indexing enabled.

The document _score is determined by the similarity between the query and document vector. See similarity for more information on how kNN search scores are computed.

To gather results, the kNN search API finds a num_candidates number of approximate nearest neighbor candidates on each shard. The search computes the similarity of these candidate vectors to the query vector, selecting the k most similar results from each shard. The search then merges the results from each shard to return the global top k nearest neighbors.

You can increase num_candidates for more accurate results at the cost of slower search speeds. A search with a high value for num_candidates considers more candidates from each shard. This takes more time, but the search has a higher probability of finding the true k top nearest neighbors.

Similarly, you can decrease num_candidates for faster searches with potentially less accurate results.

The approximate kNN search API supports byte value vectors in addition to float value vectors. Use the knn option to search a dense_vector field with element_type set to byte and indexing enabled.

If you want to provide float vectors, but want the memory savings of byte vectors, you can use the quantization feature. Quantization allows you to provide float vectors, but internally they are indexed as byte vectors. Additionally, the original float vectors are still retained in the index.

To use quantization, you can use the index type int8_hnsw object in the dense_vector mapping.

response = client.indices.create(
  index: 'quantized-image-index',
  body: {
    mappings: {
      properties: {
        "image-vector": {
          type: 'dense_vector',
          element_type: 'float',
          dims: 2,
          index: true,
          index_options: {
            type: 'int8_hnsw'
          }
        },
        title: {
          type: 'text'
        }
      }
    }
  }
)
puts response

PUT quantized-image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "element_type": "float",
        "dims": 2,
        "index": true,
        "index_options": {
          "type": "int8_hnsw"
        }
      },
      "title": {
        "type": "text"
      }
    }
  }
}

Since the original float vectors are still retained in the index, you can optionally use them for re-scoring. Meaning, you can search over all the vectors quickly using the int8_hnsw index and then rescore only the top k results. This provides the best of both worlds, fast search and accurate scoring.

response = client.search(
  index: 'quantized-image-index',
  body: {
    knn: {
      field: 'image-vector',
      query_vector: [
        0.1,
        -2
      ],
      k: 15,
      num_candidates: 100
    },
    fields: [
      'title'
    ],
    rescore: {
      window_size: 10,
      query: {
        rescore_query: {
          script_score: {
            query: {
              match_all: {}
            },
            script: {
              source: "cosineSimilarity(params.query_vector, 'image-vector') + 1.0",
              params: {
                query_vector: [
                  0.1,
                  -2
                ]
              }
            }
          }
        }
      }
    }
  }
)
puts response

POST quantized-image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [0.1, -2],
    "k": 15,
    "num_candidates": 100
  },
  "fields": [ "title" ],
  "rescore": {
    "window_size": 10,
    "query": {
      "rescore_query": {
        "script_score": {
          "query": {
            "match_all": {}
          },
          "script": {
            "source": "cosineSimilarity(params.query_vector, 'image-vector') + 1.0",
            "params": {
              "query_vector": [0.1, -2]
            }
          }
        }
      }
    }
  }
}

The kNN search API supports restricting the search using a filter. The search will return the top k documents that also match the filter query.

The following request performs an approximate kNN search filtered by the file-type field:

response = client.search(
  index: 'image-index',
  body: {
    knn: {
      field: 'image-vector',
      query_vector: [
        54,
        10,
        -2
      ],
      k: 5,
      num_candidates: 50,
      filter: {
        term: {
          "file-type": 'png'
        }
      }
    },
    fields: [
      'title'
    ],
    _source: false
  }
)
puts response

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "filter": {
      "term": {
        "file-type": "png"
      }
    }
  },
  "fields": ["title"],
  "_source": false
}

Unlike conventional query filtering, where more restrictive filters typically lead to faster queries, applying filters in an approximate kNN search with an HNSW index can decrease performance. This is because searching the HNSW graph requires additional exploration to obtain the num_candidates that meet the filter criteria.

To avoid significant performance drawbacks, Lucene implements the following strategies per segment:

You can perform hybrid retrieval by providing both the knn option and a query:

response = client.search(
  index: 'image-index',
  body: {
    query: {
      match: {
        title: {
          query: 'mountain lake',
          boost: 0.9
        }
      }
    },
    knn: {
      field: 'image-vector',
      query_vector: [
        54,
        10,
        -2
      ],
      k: 5,
      num_candidates: 50,
      boost: 0.1
    },
    size: 10
  }
)
puts response

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  "size": 10
}

This search finds the global top k = 5 vector matches, combines them with the matches from the match query, and finally returns the 10 top-scoring results. The knn and query matches are combined through a disjunction, as if you took a boolean or between them. The top k vector results represent the global nearest neighbors across all index shards.

The score of each hit is the sum of the knn and query scores. You can specify a boost value to give a weight to each score in the sum. In the example above, the scores will be calculated as

score = 0.9 * match_score + 0.1 * knn_score

The knn option can also be used with aggregations. In general, Elasticsearch computes aggregations over all documents that match the search. So for approximate kNN search, aggregations are calculated on the top k nearest documents. If the search also includes a query, then aggregations are calculated on the combined set of knn and query matches.

kNN search enables you to perform semantic search by using a previously deployed text embedding model. Instead of literal matching on search terms, semantic search retrieves results based on the intent and the contextual meaning of a search query.

Under the hood, the text embedding NLP model generates a dense vector from the input query string called model_text you provide. Then, it is searched against an index containing dense vectors created with the same text embedding machine learning model. The search results are semantically similar as learned by the model.

Reference the deployed text embedding model or the model deployment in the query_vector_builder object and provide the search query as model_text:

(...)
{
  "knn": {
    "field": "dense-vector-field",
    "k": 10,
    "num_candidates": 100,
    "query_vector_builder": {
      "text_embedding": { 
        "model_id": "my-text-embedding-model", 
        "model_text": "The opposite of blue" 
      }
    }
  }
}
(...)

For more information on how to deploy a trained model and use it to create text embeddings, refer to this end-to-end example.

In addition to hybrid retrieval, you can search more than one kNN vector field at a time:

response = client.search(
  index: 'image-index',
  body: {
    query: {
      match: {
        title: {
          query: 'mountain lake',
          boost: 0.9
        }
      }
    },
    knn: [
      {
        field: 'image-vector',
        query_vector: [
          54,
          10,
          -2
        ],
        k: 5,
        num_candidates: 50,
        boost: 0.1
      },
      {
        field: 'title-vector',
        query_vector: [
          1,
          20,
          -52,
          23,
          10
        ],
        k: 10,
        num_candidates: 10,
        boost: 0.5
      }
    ],
    size: 10
  }
)
puts response

POST image-index/_search
{
  "query": {
    "match": {
      "title": {
        "query": "mountain lake",
        "boost": 0.9
      }
    }
  },
  "knn": [ {
    "field": "image-vector",
    "query_vector": [54, 10, -2],
    "k": 5,
    "num_candidates": 50,
    "boost": 0.1
  },
  {
    "field": "title-vector",
    "query_vector": [1, 20, -52, 23, 10],
    "k": 10,
    "num_candidates": 10,
    "boost": 0.5
  }],
  "size": 10
}

This search finds the global top k = 5 vector matches for image-vector and the global k = 10 for the title-vector. These top values are then combined with the matches from the match query and the top-10 documents are returned. The multiple knn entries and the query matches are combined through a disjunction, as if you took a boolean or between them. The top k vector results represent the global nearest neighbors across all index shards.

The scoring for a doc with the above configured boosts would be:

score = 0.9 * match_score + 0.1 * knn_score_image-vector + 0.5 * knn_score_title-vector

While kNN is a powerful tool, it always tries to return k nearest neighbors. Consequently, when using knn with a filter, you could filter out all relevant documents and only have irrelevant ones left to search. In that situation, knn will still do its best to return k nearest neighbors, even though those neighbors could be far away in the vector space.

To alleviate this worry, there is a similarity parameter available in the knn clause. This value is the required minimum similarity for a vector to be considered a match. The knn search flow with this parameter is as follows:

For each configured similarity, here is the corresponding inverted _score function. This is so if you are wanting to filter from a _score perspective, you can do this minor transformation to correctly reject irrelevant results.

Here is an example. In this example we search for the given query_vector for k nearest neighbors. However, with filter applied and requiring that the found vectors have at least the provided similarity between them.

response = client.search(
  index: 'image-index',
  body: {
    knn: {
      field: 'image-vector',
      query_vector: [
        1,
        5,
        -20
      ],
      k: 5,
      num_candidates: 50,
      similarity: 36,
      filter: {
        term: {
          "file-type": 'png'
        }
      }
    },
    fields: [
      'title'
    ],
    _source: false
  }
)
puts response

POST image-index/_search
{
  "knn": {
    "field": "image-vector",
    "query_vector": [1, 5, -20],
    "k": 5,
    "num_candidates": 50,
    "similarity": 36,
    "filter": {
      "term": {
        "file-type": "png"
      }
    }
  },
  "fields": ["title"],
  "_source": false
}

In our data set, the only document with the file type of png has a vector of [42, 8, -15]. The l2_norm distance between [42, 8, -15] and [1, 5, -20] is 41.412, which is greater than the configured similarity of 36. Meaning, this search will return no hits.

It is common for text to exceed a particular model’s token limit and requires chunking before building the embeddings for individual chunks. When using nested with dense_vector, you can achieve nearest passage retrieval without copying top-level document metadata.

Here is a simple passage vectors index that stores vectors and some top-level metadata for filtering.

response = client.indices.create(
  index: 'passage_vectors',
  body: {
    mappings: {
      properties: {
        full_text: {
          type: 'text'
        },
        creation_time: {
          type: 'date'
        },
        paragraph: {
          type: 'nested',
          properties: {
            vector: {
              type: 'dense_vector',
              dims: 2
            },
            text: {
              type: 'text',
              index: false
            }
          }
        }
      }
    }
  }
)
puts response

PUT passage_vectors
{
    "mappings": {
        "properties": {
            "full_text": {
                "type": "text"
            },
            "creation_time": {
                "type": "date"
            },
            "paragraph": {
                "type": "nested",
                "properties": {
                    "vector": {
                        "type": "dense_vector",
                        "dims": 2
                    },
                    "text": {
                        "type": "text",
                        "index": false
                    }
                }
            }
        }
    }
}

With the above mapping, we can index multiple passage vectors along with storing the individual passage text.

response = client.bulk(
  index: 'passage_vectors',
  refresh: true,
  body: [
    {
      index: {
        _id: '1'
      }
    },
    {
      full_text: 'first paragraph another paragraph',
      creation_time: '2019-05-04',
      paragraph: [
        {
          vector: [
            0.45,
            45
          ],
          text: 'first paragraph',
          paragraph_id: '1'
        },
        {
          vector: [
            0.8,
            0.6
          ],
          text: 'another paragraph',
          paragraph_id: '2'
        }
      ]
    },
    {
      index: {
        _id: '2'
      }
    },
    {
      full_text: 'number one paragraph number two paragraph',
      creation_time: '2020-05-04',
      paragraph: [
        {
          vector: [
            1.2,
            4.5
          ],
          text: 'number one paragraph',
          paragraph_id: '1'
        },
        {
          vector: [
            -1,
            42
          ],
          text: 'number two paragraph',
          paragraph_id: '2'
        }
      ]
    }
  ]
)
puts response

POST passage_vectors/_bulk?refresh=true
{ "index": { "_id": "1" } }
{ "full_text": "first paragraph another paragraph", "creation_time": "2019-05-04", "paragraph": [ { "vector": [ 0.45, 45 ], "text": "first paragraph", "paragraph_id": "1" }, { "vector": [ 0.8, 0.6 ], "text": "another paragraph", "paragraph_id": "2" } ] }
{ "index": { "_id": "2" } }
{ "full_text": "number one paragraph number two paragraph", "creation_time": "2020-05-04", "paragraph": [ { "vector": [ 1.2, 4.5 ], "text": "number one paragraph", "paragraph_id": "1" }, { "vector": [ -1, 42 ], "text": "number two paragraph", "paragraph_id": "2" } ] }

The query will seem very similar to a typical kNN search:

response = client.search(
  index: 'passage_vectors',
  body: {
    fields: [
      'full_text',
      'creation_time'
    ],
    _source: false,
    knn: {
      query_vector: [
        0.45,
        45
      ],
      field: 'paragraph.vector',
      k: 2,
      num_candidates: 2
    }
  }
)
puts response

POST passage_vectors/_search
{
    "fields": ["full_text", "creation_time"],
    "_source": false,
    "knn": {
        "query_vector": [
            0.45,
            45
        ],
        "field": "paragraph.vector",
        "k": 2,
        "num_candidates": 2
    }
}

Note below that even though we have 4 total vectors, we still return two documents. kNN search over nested dense_vectors will always diversify the top results over the top-level document. Meaning, "k" top-level documents will be returned, scored by their nearest passage vector (e.g. "paragraph.vector").

{
    "took": 4,
    "timed_out": false,
    "_shards": {
        "total": 1,
        "successful": 1,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": {
            "value": 2,
            "relation": "eq"
        },
        "max_score": 1.0,
        "hits": [
            {
                "_index": "passage_vectors",
                "_id": "1",
                "_score": 1.0,
                "fields": {
                    "creation_time": [
                        "2019-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "first paragraph another paragraph"
                    ]
                }
            },
            {
                "_index": "passage_vectors",
                "_id": "2",
                "_score": 0.9997144,
                "fields": {
                    "creation_time": [
                        "2020-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "number one paragraph number two paragraph"
                    ]
                }
            }
        ]
    }
}

What if you wanted to filter by some top-level document metadata? You can do this by adding filter to your knn clause.

response = client.search(
  index: 'passage_vectors',
  body: {
    fields: [
      'creation_time',
      'full_text'
    ],
    _source: false,
    knn: {
      query_vector: [
        0.45,
        45
      ],
      field: 'paragraph.vector',
      k: 2,
      num_candidates: 2,
      filter: {
        bool: {
          filter: [
            {
              range: {
                creation_time: {
                  gte: '2019-05-01',
                  lte: '2019-05-05'
                }
              }
            }
          ]
        }
      }
    }
  }
)
puts response

POST passage_vectors/_search
{
    "fields": [
        "creation_time",
        "full_text"
    ],
    "_source": false,
    "knn": {
        "query_vector": [
            0.45,
            45
        ],
        "field": "paragraph.vector",
        "k": 2,
        "num_candidates": 2,
        "filter": {
            "bool": {
                "filter": [
                    {
                        "range": {
                            "creation_time": {
                                "gte": "2019-05-01",
                                "lte": "2019-05-05"
                            }
                        }
                    }
                ]
            }
        }
    }
}

Now we have filtered based on the top level "creation_time" and only one document falls within that range.

{
    "took": 4,
    "timed_out": false,
    "_shards": {
        "total": 1,
        "successful": 1,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": {
            "value": 1,
            "relation": "eq"
        },
        "max_score": 1.0,
        "hits": [
            {
                "_index": "passage_vectors",
                "_id": "1",
                "_score": 1.0,
                "fields": {
                    "creation_time": [
                        "2019-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "first paragraph another paragraph"
                    ]
                }
            }
        ]
    }
}

Additionally, if you wanted to extract the nearest passage for a matched document, you can supply inner_hits to the knn clause.

response = client.search(
  index: 'passage_vectors',
  body: {
    fields: [
      'creation_time',
      'full_text'
    ],
    _source: false,
    knn: {
      query_vector: [
        0.45,
        45
      ],
      field: 'paragraph.vector',
      k: 2,
      num_candidates: 2,
      inner_hits: {
        _source: false,
        fields: [
          'paragraph.text'
        ]
      }
    }
  }
)
puts response

POST passage_vectors/_search
{
    "fields": [
        "creation_time",
        "full_text"
    ],
    "_source": false,
    "knn": {
        "query_vector": [
            0.45,
            45
        ],
        "field": "paragraph.vector",
        "k": 2,
        "num_candidates": 2,
        "inner_hits": {
            "_source": false,
            "fields": [
                "paragraph.text"
            ]
        }
    }
}

Now the result will contain the nearest found paragraph when searching.

{
    "took": 4,
    "timed_out": false,
    "_shards": {
        "total": 1,
        "successful": 1,
        "skipped": 0,
        "failed": 0
    },
    "hits": {
        "total": {
            "value": 2,
            "relation": "eq"
        },
        "max_score": 1.0,
        "hits": [
            {
                "_index": "passage_vectors",
                "_id": "1",
                "_score": 1.0,
                "fields": {
                    "creation_time": [
                        "2019-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "first paragraph another paragraph"
                    ]
                },
                "inner_hits": {
                    "paragraph": {
                        "hits": {
                            "total": {
                                "value": 1,
                                "relation": "eq"
                            },
                            "max_score": 1.0,
                            "hits": [
                                {
                                    "_index": "passage_vectors",
                                    "_id": "1",
                                    "_nested": {
                                        "field": "paragraph",
                                        "offset": 0
                                    },
                                    "_score": 1.0,
                                    "fields": {
                                        "paragraph": [
                                            {
                                                "text": [
                                                    "first paragraph"
                                                ]
                                            }
                                        ]
                                    }
                                }
                            ]
                        }
                    }
                }
            },
            {
                "_index": "passage_vectors",
                "_id": "2",
                "_score": 0.9997144,
                "fields": {
                    "creation_time": [
                        "2020-05-04T00:00:00.000Z"
                    ],
                    "full_text": [
                        "number one paragraph number two paragraph"
                    ]
                },
                "inner_hits": {
                    "paragraph": {
                        "hits": {
                            "total": {
                                "value": 1,
                                "relation": "eq"
                            },
                            "max_score": 0.9997144,
                            "hits": [
                                {
                                    "_index": "passage_vectors",
                                    "_id": "2",
                                    "_nested": {
                                        "field": "paragraph",
                                        "offset": 1
                                    },
                                    "_score": 0.9997144,
                                    "fields": {
                                        "paragraph": [
                                            {
                                                "text": [
                                                    "number two paragraph"
                                                ]
                                            }
                                        ]
                                    }
                                }
                            ]
                        }
                    }
                }
            }
        ]
    }
}

For approximate kNN search, Elasticsearch stores the dense vector values of each segment as an HNSW graph. Indexing vectors for approximate kNN search can take substantial time because of how expensive it is to build these graphs. You may need to increase the client request timeout for index and bulk requests. The approximate kNN tuning guide contains important guidance around indexing performance, and how the index configuration can affect search performance.

In addition to its search-time tuning parameters, the HNSW algorithm has index-time parameters that trade off between the cost of building the graph, search speed, and accuracy. When setting up the dense_vector mapping, you can use the index_options argument to adjust these parameters:

response = client.indices.create(
  index: 'image-index',
  body: {
    mappings: {
      properties: {
        "image-vector": {
          type: 'dense_vector',
          dims: 3,
          similarity: 'l2_norm',
          index_options: {
            type: 'hnsw',
            m: 32,
            ef_construction: 100
          }
        }
      }
    }
  }
)
puts response

PUT image-index
{
  "mappings": {
    "properties": {
      "image-vector": {
        "type": "dense_vector",
        "dims": 3,
        "similarity": "l2_norm",
        "index_options": {
          "type": "hnsw",
          "m": 32,
          "ef_construction": 100
        }
      }
    }
  }
}

To run an exact kNN search, use a script_score query with a vector function.