When is exact kNN still the right choice in Elasticsearch, and what does approximate kNN cost?

Zalando's public Elasticsearch upgrade post gives this as the main product reason for moving from 7.17 to 8.x: the team already used vector search, but only the exact, brute-force kind, and wanted approximate kNN. That makes the trade-off a natural interview topic.

Exact kNN. A script_score query (or the exact dense_vector query) computes the vector similarity for every document that matches the surrounding query. Elastic's docs say it "guarantees accurate results but does not scale well for large datasets", and that latency improves if a filter narrows the set first. So exact kNN is right when the candidate set is already small: one merchant's assortment, a single category after strict filters, a re-ranking step over a few hundred lexical hits, or an evaluation job that needs the true neighbours as ground truth.

Approximate kNN. The top-level knn search uses a vector index (HNSW graphs, optionally with quantization) to visit only a fraction of the vectors. Elastic recommends it for most production workloads "where low latency and scale matter more than perfect recall". The costs:

• Indexing. The dense_vector docs call indexing vectors for approximate search "an expensive process" that can take substantial time; every segment builds its own graph, and merges rebuild them.
• Memory. The graphs want to live in the OS page cache for good latency, which competes with everything else on the node. Quantization reduces that footprint at some cost in precision. Which index type and quantization you get by default depends on the Elasticsearch version and the vector element type, so check the version's dense_vector docs rather than assuming.
• Recall. Results are approximate. k is the number of neighbours returned, and num_candidates is "the number of nearest neighbor candidates to consider per shard". Raising num_candidates improves recall and costs latency.

Filtering. Put structured filters (category, size, in stock, market) in the kNN search's filter option so the search looks for the nearest neighbours among documents that pass the filter. Filtering the top results afterwards can leave fewer than k hits or none at all.

Hybrid retrieval. In product search, vectors usually complement lexical matching rather than replace it: exact brand and size tokens matter. Combine a lexical query and a knn leg, and fuse with a rank-based method or a weighted score, then evaluate offline before shipping.

How to tune honestly. Compute exact neighbours for a sample of real queries with brute force, then measure the recall of approximate search at several num_candidates values against latency. Pick the knee of the curve, not a number from a blog post.

Alternate interview scenarios