Elasticsearch Vector Search

The dense_vector field and the baseline you approximate

A dense_vector field with index: true tells Lucene to build an approximate-nearest-neighbour structure over your embeddings. The question that structure answers is exact k-NN: over N vectors of dimension d, score each against the query and keep the best k.

V: [N, d]   q: [d]
score_i = sim(q, V_i)   for i = 1 .. N
cost = O(N * d)   memory = N * d * 4 bytes (float32)

With N = 5,000,000 and d = 1024, one exact query is 5e6 × 1024 ≈ 5.1 billion multiply-adds — hundreds of milliseconds of pure arithmetic. Elasticsearch will do this if you ask (a script_score over a non-indexed vector), and for small or tightly filtered sets it is the right answer. But the cost is linear in N, and HNSW turns that scan into a logarithmic descent, at the price of occasionally returning a neighbour that is excellent rather than provably best.

HNSW, but living inside a Lucene segment

Hierarchical Navigable Small World builds a layered proximity graph. Each vector becomes a node; a node’s top layer is drawn from an exponential distribution so upper layers are sparse long-range sketches and layer 0 holds everything:

P(level ≥ l) ≈ m^(-l)   →  layer l holds ≈ N / m^l nodes
expected layers  ≈ log_m(N)
search: enter at top, greedily walk to the closest neighbour, refine at layer 0

The Lucene twist is that this graph is not global. Lucene writes documents into segments — small, immutable mini-indexes flushed as you index — and each segment builds its own independent HNSW graph over just the vectors it contains. A shard with twenty segments holds twenty separate graphs, and nothing links them. That keeps writes append-only and lock-free, but it means a single logical index is really a committee of small graphs, each consulted separately.

m and ef_construction: the build-time dials

Two index_options parameters shape each segment’s graph. m is the maximum number of neighbour connections per node (layer 0 allows up to 2 × m); ef_construction is the beam width used while inserting a vector during the build.

The asymmetry is the whole tuning story. ef_construction is a one-off tax paid at build (and re-paid at every merge) that raises graph quality forever, so generosity there is cheap. m raises recall but also the permanent memory footprint of every graph and the merge cost. Neither can change without reindexing.

Segment merging: the write cost that HNSW hides

Because segments are immutable and each carries a full graph, deletes are tombstones and updates are delete-plus-append. Left alone, a shard accumulates hundreds of small segments — and search cost grows with segment count. Lucene’s TieredMergePolicy fights this by merging small segments into larger ones in the background.

Here is the sting specific to vectors: two HNSW graphs cannot be concatenated. A merged segment’s graph must be rebuilt by re-inserting the combined vectors, at roughly O(n · ef_construction · log n) distance computations for n vectors. So every vector you index is effectively inserted into a graph many times over its lifetime, once per merge tier it passes through — classic write amplification, but measured in graph builds. This is why bulk-loading vectors is CPU-heavy, and why a force_merge to one segment gives the best recall and latency but is expensive — do it once after the bulk load, never during.

num_candidates and searching a committee of graphs

A knn query names k (results wanted) and num_candidates (the working-set size). Because every segment is searched independently, the fan-out is per-segment: each of a shard’s segments runs its own greedy walk collecting up to num_candidates local candidates, the shard keeps its top num_candidates, and the coordinating node reduces the per-shard results to the top k.

per segment : greedy HNSW walk, beam ≈ num_candidates
per shard   : merge segment tops → keep num_candidates
coordinator : merge shard tops    → keep k

Two consequences follow. Recall improves as num_candidates grows but with sharply diminishing returns, so tune it against an exact run. And many small segments cost more than one large one, since the beam-width work repeats per graph — another reason fewer segments search faster.

Filtered kNN and the exact-search fallback

Real queries want the nearest neighbours among documents that also match a predicate — a tenant id, a date range. Elasticsearch supports a filter inside the knn clause, and it is a genuine pre-filter: Lucene turns the predicate into a matching bit set and the graph walk only accepts nodes in that set, rather than searching first and discarding non-matches afterward.

But a graph built over all N points has edges chosen for the unfiltered space. Mask out most nodes and the subgraph fragments — a node with 2m neighbours keeps only about 2m × s live ones for selectivity s, and below a percent or so the greedy walk stalls in disconnected islands. Lucene handles this with a threshold: when the filtered set is small relative to the work an approximate walk would do, it abandons the graph and runs an exact brute-force scan over just the matching documents — fast and exactly correct because the survivor set is tiny. Selective filter plus small survivor set equals exact search, and Elasticsearch makes that switch for you.

Hybrid retrieval: BM25 and kNN through reciprocal rank fusion

Vectors capture semantic similarity; BM25 captures exact lexical matches like product codes and rare terms. The two score on incompatible scales — a BM25 score of 14.2 and a cosine of 0.83 cannot simply be added — so Elasticsearch combines them with reciprocal rank fusion, which discards the scores and fuses the ranks:

RRF(d) = Σ_r  1 / (rank_constant + rank_r(d))     rank_constant default = 60

  ranked  1 by BM25, 3 by kNN  → 1/61 + 1/63 = 0.0323
  ranked 50 by BM25, 2 by kNN  → 1/110 + 1/62 = 0.0252

The rank_constant damps the influence of top ranks: a large constant lets deep results still contribute, a small one makes the very top dominate. Because RRF needs only ordinal ranks, it is robust to the wildly different score distributions of lexical and vector search — no normalization, no per-query tuning — which is why it is the default in the rrf retriever.

Scalar quantization: int8 and int4

The vectors, not the graph, dominate memory, so compressing them is the highest-leverage change available. Scalar quantization maps each float32 component onto a small integer using bounds learned per segment:

int8:  q_j = round( (v_j - lo) / (hi - lo) * 127 )     4x smaller
int4:  packed into 4 bits, two per byte               8x smaller
raw float32 vectors kept on disk for rescoring

Choosing index_options.type: int8_hnsw shrinks the resident vector data roughly 4×; int4_hnsw roughly 8×. Neither touches the incompressible graph, so the total shrinks less than the vector-only ratio — the graph is a floor. The key detail: Lucene keeps the full-precision vectors on disk, so quantized distances drive the fast graph walk and the raw vectors are read back only to rescore a few candidates, which keeps recall high despite an aggressively lossy index.

BBQ and oversampled rescoring

Better Binary Quantization (bbq_hnsw) pushes each dimension down to about one bit, roughly a 32× reduction, with two ideas that keep it from being naive sign-bit hashing: small per-vector correction terms de-bias the binary dot product toward the true value, and the query is quantized asymmetrically at higher precision so the query side loses almost nothing.

One bit per dimension is still lossy, so BBQ is paired with rescoring, exposed as rescore_vector with an oversample factor:

oversample = 3, k = 10
  1. HNSW walk on 1-bit vectors  → fetch 30 candidates (cheap, in RAM)
  2. rescore those 30 against full float32 vectors (one disk read)
  3. keep the true top 10

The pattern is the one that makes int4 and int8 safe, just more extreme: traverse in a tiny quantized space that fits in memory, then spend one small full-fidelity read to fix the ranking. BBQ with modest oversampling routinely holds recall in the nineties at a fraction of the RAM.

The RAM model that decides your bill

Lucene stores vectors and graphs off-heap and relies on the operating system’s filesystem cache to keep them resident. A graph walk is a chain of random reads with no locality, so the moment the hot data does not fit in RAM the latency distribution falls off a cliff. Sizing reduces to: how many bytes must stay cached?

vector bytes = N * d * B     B = 4 (fp32), 1 (int8), 0.5 (int4), 1/8 (bbq)
graph bytes  ≈ N * 2m * 4    (layer-0 neighbour ids)

N = 20e6, d = 1024, m = 16:
  fp32 : 81.9 + 2.6 = 84.5 GB
  int8 : 20.5 + 2.6 = 23.1 GB
  bbq  :  2.6 + 2.6 =  5.2 GB   (+ raw fp32 on disk for rescore)

Keep the quantized vectors plus graph comfortably inside RAM on the data nodes, leave headroom for the JVM heap, and let the full-precision vectors live on fast disk for rescoring only. Compress until the working set fits, then stop — further quantization only spends recall for no cache benefit.

Pitfalls that follow directly from the design

Each of these is a production failure that the maths above predicts:

The unifying theme is that approximate search degrades quietly: a fragmented subgraph or a cache miss lowers recall or raises tail latency without ever throwing an error. The only real defence is measurement — keep a few hundred labelled queries, run them against an exact baseline, and track recall as a first-class metric next to latency.