How Elasticsearch auto-tunes vector quantization to hit your recall target

Try out vector search for yourself using this self-paced hands-on learning for Search AI. You can start a free cloud trial or try Elastic on your local machine now.

What makes a good vector store?

A vector store that achieves good performance without tuning is more valuable than one that requires expert tuning. In fact, our contention is a data store that can be coaxed to exceptional performance by an expert who spends a week hand-tuning it is less useful than one that beats it consistently out of the box. In other words, easily achieving good performance is a first class property, not a nice to have. We can see this clearly in our telemetry. The great majority of users will never tune the internals of vector search at all, and why should they: it is just an enabler for what they're trying to build.

This is the imperative behind features like auto-calibration. The system as a whole should look at your data and your quality target and choose good parameters for you. Indeed we think this is a win-win, since it has far more nuanced information available to it to make these choices than we expose.

To make "good performance" precise, it helps to name the three attributes that characterize any vector search system, because they trade off against one another and you can't talk about one without fixing the others:

1. Performance: throughput (QPS), latency, and so on.
2. Hardware cost: a fair comparison always holds cost fixed. It's trivial to buy your way to more QPS or better recall by throwing hardware at the problem; the interesting question is what you achieve per dollar.
3. Search quality: recall, nDCG, and related measures of whether you're returning the right results.

The three form a frontier. Push one and, at fixed budget, you pay in another. Any honest comparison of approaches pins two down and measures the third. What we describe in this post is the mechanism we're introducing to pick quantization parameters for a fixed recall budget. It is a step on a longer journey towards a vector store that configures itself well across the board.

Why recall is the right quality metric for vector search

Search quality is tricky, because the "right" results depend on relevance labels you usually don't have at index time. So we lean on recall as a safe proxy. The argument is simple: recall measures how well the approximate index reproduces the results of exact search over the same embeddings. If recall is high, you have not degraded search quality relative to what the underlying model can do; you can be confident you’ve faithfully preserved the baseline. You might still wish for a better embedding model, we've got you covered, but that's a separate concern from the index not damaging what the model already gives you.

This is why controlling recall matters so much, and why you should be wary of any system that doesn't reliably control it. If a vendor can't control recall, they can silently degrade your search experience, achieving impressive QPS numbers while quietly returning worse results, and you'd have no way to know without a labeled evaluation set. The method in this post is about maximizing performance while keeping a firm, predictable grip on quality.

Why vector quantization parameters must be chosen at index time

What makes the problem genuinely hard is that vectors are quantized as they are indexed, so the parameters that govern quality (how many bits, how deep to rerank, whether to precondition) have to be evaluated before we've seen the data laid out in its final form. We can't index everything, measure recall, and iterate; by then the quantization is baked in.

So we need to estimate what we'll need from a small sample, cheaply and in advance. Fortunately the Elasticsearch gives us natural moments to do this: segment merges are exactly such an opportunity. When segments are combined we have to rewrite the data anyway and can assess the data and (re)choose parameters. And as we'll see, models fit to small random samples give excellent estimates of the quantities we actually need to control. They’re typically good enough to set parameters once, with a small margin, and trust them as the index grows.

How vector quantization affects nearest-neighbor recall

With that motivation in place, let's start to dig into the details.

Vector quantization is a critical component for making approximate nearest-neighbor (ANN) search affordable at scale; it's an area we've innovated in the past. Instead of storing and comparing full-precision embeddings, we store a lossy, compressed representation and search over that. The catch is the one above: lossy representations move distances around, so the "nearest" neighbors under quantized distances are not always the true nearest neighbors and recall suffers.

The standard fix is to over-retrieve and rerank. We use the cheap quantized distances to pull back the top $n$ candidates, then recompute exact distances for those $n$ and keep the best $k$. As long as the true top-$k$ are present somewhere in the retrieved top-$n$, reranking recovers them exactly.

Reranking isn’t free, we have to fetch high precision vectors from disk. However, we can precisely characterize the performance of reranking based on hardware characteristics alone. This reframes the whole problem. The question is no longer "how much does quantization distort distances?" in the abstract, but something which relates back to the attributes we care about:

Given a quantization scheme with some error magnitude, and a rerank budget of $n$ candidates, what recall@$k$ should we expect. As an immediate consequence, what is the cheapest set of parameters that hits our recall target?

This post derives a model that answers exactly that. The core of it is a single, surprisingly clean idea: if we can characterize the distribution of distances to the $k$-th nearest neighbor, and we have a model of the quantization error distribution, then we can compute expected recall after reranking in closed form (up to a one-dimensional integral). Everything else – bit counts, rerank depth, whether to precondition – becomes a search over a model we can fit cheaply from a small sample, instead of an expensive empirical sweep over full indices built with those parameters.

We build it up to this in three stages: the geometry of nearest-neighbor distances, the scaling law that falls out of it, and then the recall model that ties quantization error to recall given a reranking budget. Be warned, the following gets a little bit involved, but to give you intuition about what is happening see the video below.

Quantization error vs. the nearest-neighbor distance gap

Fix a query $q$ and rank the database vectors by their true distance to it: $R_{(1)} \le R_{(2)} \le \dots$, so $R_{(i)}$ is the distance to the $i$-th nearest neighbor. Reranking the top $n$ succeeds for the true $k$-th neighbor whenever it is not pushed past rank $n$ by quantization noise.

Two competing quantities govern this:

• The quantization error that is essentially fixed for a given scheme and dataset: it depends on the embedding dimension, the vector distribution, and the number of bits, but not on how big the index is.
• The criticality gap $\Delta_{k,n} = R_{(n)} - R_{(k)}$, which is the distance between the $k$-th and the $n$-th nearest neighbor. This is the margin we have to absorb error. Crucially, it shrinks as the index grows: pack more vectors into the same region and neighbors crowd together.

There’s a detail here we’ll gloss over for the sake of presentation: for IVF style indices, we’re quantizing the residual from a cluster’s centroid. This does in fact couple the quantization error to the index size, but we can handle it much the same way we handle the distance to the $i$-th nearest neighbor.

For reranking to recover the recall lost to quantization, we need the error to only rarely exceed the gap. If we can write down the distribution of $\Delta_{k,n}$ and the distribution of the error, we can make that statement quantitative. The first job is to estimate the distribution of nearest-neighbor distances.

Deriving the nearest-neighbor distance distribution

Real embeddings don't fill their ambient space; they concentrate on a lower-dimensional manifold. Near a query, though, we can make a mild local assumption: in a small neighborhood $\Omega \subset \mathbb{R}^d$ around the query, the data density is roughly uniform. Here $d$ is the intrinsic dimension of the manifold; it is unknown and generally far smaller than the embedding dimension. How to estimate it is the subject of Section 4.

Let $\mathcal{X} = \{X_i\}$ be the $N$ vectors falling in $\Omega$, modeled as i.i.d. uniform on $\Omega$, and define the distance from $q$ to its nearest neighbor:

To get the distribution of $R$ we use the standard order-statistics trick: rather than ask where the minimum is, ask for the probability it exceeds some radius $r$. The event $\{R > r\}$ is exactly the event that every point lands outside the $d$-ball centered on the query $B_r(q)$.

A single point lands inside $B_r(q)$ with probability equal to the ratio of the ball's volume to the region's volume $V$

where $\omega_d$ is the volume of the unit $d$-ball. (We assume $N$ is large enough that the relevant $r$ is small, so the ball doesn't spill outside $\Omega$ and boundary effects are negligible.) Because the points positions are assumed to be independent, the survival function is

What we're really interested in is how R behaves on average. To compute this, we use the identity that the expectation of a non-negative random variable is the integral of its survival function, $\mathbb{E}[R] = \int_0^\infty P(R > r)\, dr$. Evaluating this with (2) gives the headline result:

(The exact integral carries an extra $\Gamma(1 + 1/d)$ factor; it's an $O(1)$ constant that we can fold into a fitted coefficient later, so we drop it here.)

Glacial scaling: why neighbor distances barely change as your index grows

It is interesting to consider what this formula tells us about how distances change with dataset size: $\mathbb{E}[R] \propto N^{-1/d}$. The exponent is $-1/d$, and in high intrinsic dimensions that is a very small number. This is a property the method leans on, so it's worth plugging in some numbers:

• If $d = 2$ then doubling $N$ multiplies $\mathbb{E}[R]$ by $2^{-1/2} \approx 0.707$, so distances drop by ~30%.
• If $d = 50$ then doubling $N$ multiplies $\mathbb{E}[R]$ by $2^{-1/50} \approx 0.986$, so distances drop by a little over 1%.

In high dimensions, neighbor distances barely move even if you add a lot of data; call it glacial scaling. It's the reason we can choose quantization parameters once from a tiny sample, with a small safety margin, and trust them to remain valid even after the index grows substantially before the next re-quantization.

Expected distance to the k-th neighbor and the criticality gap

We actually care about the whole sequence of order statistics $R_{(k)}$, $R_{(n)}$, not just the minimum. There's a simple way to get them.

Map each radius to the cumulative volume it encloses by defining

By (1), each $U_i$ is exactly the probability of landing within radius $R_i$, so the $\{U_i\}$ are uniform on $[0,1]$. The order statistics of uniforms are textbook: the $i$-th smallest of $N$ uniforms follows a Beta distribution,

Inverting the volume map, $R_{(i)} \propto U_{(i)}^{1/d}$, gives the scaling of the $i$-th neighbor distance:

That's all we need for the expected gap:

The last form is the intuitive one: the gap between the $k$-th and $n$-th neighbors is the distance to the $k$-th neighbor, scaled by $\big((n/k)^{1/d} - 1\big)$. Widening the rerank depth $n$ relative to $k$ opens the gap; higher intrinsic dimension $d$ closes it (the exponent $1/d$ pushes $(n/k)^{1/d}$ toward 1).

Why the expected gap is sufficient to predict recall

Working with an expectation is only legitimate if the gap doesn't fluctuate wildly around it. It doesn't because concentration of measure saves us. Applying the delta method to $R_{(k)} \propto U_{(k)}^{1/d}$ and using $\mathrm{Var}(U_{(k)}) \approx k/N^2$ from the Beta distribution, a little algebra gives

So the coefficient of variation is about $\frac{1}{d\sqrt{k}}$. For any reasonable intrinsic dimension this is negligible, which justifies modeling only the expected distances. (If you're worried about the delta method approximation, you can check the results numerically: the delta-method variance and the resulting $1/(d\sqrt{k})$ coefficient of variation match the exact expressions to several significant figures.)

Extending the model to cosine similarity and inner product search

The derivation is for the Euclidean metric, but the other common metrics reduce to it:

• For cosine similarity, the equidistant surface is the intersection of a sphere around the query with the unit sphere. This is called a hyperspherical cap, whose volume scales as $\sin(\theta)^{d-1} \approx \theta^{d-1}$ for small $\theta$. Therefore, the analysis carries over unchanged up to constants, with the dimension reduced by one.
• For MIPS (maximum inner product), some extra care is needed, because nearest neighbors aren't confined to a compact region. A distant vector can still win on inner product if its norm is large enough, so the gap is really governed by the tail of the norm distribution. However, there is a clean fix, which is to use the Neyshabur–Srebro transformation. This lifts vectors onto a unit hypersphere in $d+1$ dimensions. After this operation, it's just the cosine case.

Fitting intrinsic dimension and scale from a small sample

Equation (3) has a known functional form but two unknown parameters: the intrinsic dimension $d$ and the scale $\alpha$. Both are easy to fit, and it's more convenient to fit them from raw neighbor distances than from gaps directly.

Sample several subsets of database vectors $\{D_i\}$ of sizes $N_i = |D_i|$ and a set of query vectors $Q$. For each query $q\in Q$ and each subset, measure $r_{i,j}(q)$, the distance to the $j$-th nearest neighbor of $q$ within $D_i$. Taking logs of the scaling law $\mathbb{E}[R_{(j)}] \approx \alpha (j\,/\,N_i)^{1/d}$ linearises it:

Specifically, this is linear in $\log j$ and $\log(N_i/N_0)$, so ordinary least squares recovers $\hat{\alpha}$ and $\hat{d}$. Varying the subset size $N_i$ is what makes it possible to estimate $d$: it's precisely the rate at which distances shrink with data volume. With the fitted parameters, the whole-index expected gap is

Figure 1 shows how well this fits in practice (and it’s remarkably good): predicted versus actual average distance to the $k$-th neighbor, across a range of datasets and metrics, have $R^2$ between 0.996 and 0.999.

Modeling vector quantization error as Gaussian

With the nearest-neighbor distance model established, the second component is the quantization error distribution. For every metric we use, the quantized distance estimate differs from the true distance by an error that is a sum of many independent per-dimension contributions. By the Central Limit Theorem that sum tends to Gaussian, so we model the error as normal with a variance we estimate empirically:

where $\tilde{r}_{i,j}(q \mid b)$ is the quantized distance estimate using $b$-bit vectors and $Z$ is the total number of (query, neighbor) pairs in our sample set. In other words: sample, quantize, measure the squared distance errors, average.

Figure 2 shows the empirical basis for the Gaussian assumption: measured quantization error densities against best-fit Gaussians across a variety of datasets. The fit is good, which is what lets the rest of the model stay analytic.

We could stop here and take a minimax view: threshold the probability that the $k$-th and $n$-th neighbors swap, using the expected gap (4) against the error scale $\sigma_b$. But that controls a worst-case event, and what we actually want to control is average recall. The outcome would be overly conservative quantization parameters and we'd pay some performance. The next section estimates expected recall properly.

Predicting expected recall after reranking

Combining the distance model and the error model gives a closed-form estimate of expected recall after reranking. Model the noisy distance of the $i$-th true neighbor as a Gaussian centered on its true distance:

The $i$-th neighbor survives reranking, i.e., lands in the retrieved top $n$, if fewer than $n$ other vectors have a smaller noisy distance. Condition on $X_i = x$ and count the competitors closer than $x$:

Then the probability of recalling neighbor $i$ integrates over where its own noisy distance lands:

The terms of $S(x)$ are independent Bernoullis but not identically distributed, since every neighbor $j$ sits at a different true distance $R_{(j)}$, so each has its own probability of intruding on the top-$k$ set:

with $\Phi$ the standard normal CDF. This makes $S(x)$ a Poisson-binomial variable. Since we sum many of them (because $N \gg n$), the Lyapunov CLT applies and we approximate

with the standard Poisson-binomial moments

The survival probability then has a clean closed form:

This is where the two halves of the post so far finally meet. We don't need to know the individual $R_{(j)}$ because the manifold scaling law from Section 3 supplies them: $R_{(j)} = \alpha\,(jN_0/N)^{1/d}$. So the moments become explicit sums over ranks, which we truncate at a safe cutoff (say $10n$, since distant neighbors contribute negligibly):

Finally, average recall@$k$ given rerank depth $n$ sums the per-neighbor recall over the top $k$:

Here $\phi$ is the standard normal density. Each integral is smooth and one-dimensional, so Gauss–Legendre quadrature evaluates it in microseconds. The entire recall prediction for a set of candidate parameters costs a handful of quadrature evaluations, not index build and benchmark run.

Figure 3 validates the end-to-end model: predicted average recall against measured recall across many parameter settings and multiple datasets has $R^2 = 0.982$.

How the recall model selects vector quantization parameters

With a fast recall predictor available, parameter selection becomes a cheap ordered search. Given a target recall and a rerank budget $n$ (typically expressed as a multiple of $k$), we can find the minimum document and query bit counts, and other knobs, that clear the target. There are a few things to note that are practically important:

1. Glacial scaling gives us some safety because $R_{(k)}$ moves so slowly with $N$ for even moderate intrinsic dimension. A small margin in the calculation means the chosen parameters stay valid if a lot of vectors are added before parameters are restimated.
2. Small $k$ is the worst case if $n$ is a fixed multiple of $k$. The gap \mathbb{E}[R_{(k)}]($(n/k)^{1/d} - 1)$ is smallest for small $k$ so if a parameter choice satisfies the recall target at $k = 10$ then it will for larger $k$ will too.
3. We can treat quantization as a black box because the error model only needs the empirical error variance. This means we can test any configuration, including preconditioning, the same way and we can simply order candidate parameter tuples by increasing index and query cost, and stop at the first choice that hits the target recall. For tuples of (query bits, doc bits, rerank depth, precondition) a sensible search sequence increases query precision first, then document precision $(1,1)$, $(2,1)$, $(3,1)$, $(4,1)$, $(2,2)$, $(3,3)$, $(4,2)$, $(4,4)$, $(7,4)$ and $(7,7)$ each combined (via an outer product $\otimes$) with rerank depths like $(1.5k,\,2k,\,3k)$ and precondition $\in \{\text{true},\, \text{false}\}$, exiting as soon as the target is met.

Results: auto-selected quantization parameters and recall across datasets

In this section, we discuss the results of the initial experiments on the end-to-end behavior. We’ve made some further refinements as part of the work to fully integrate with Elasticsearch that we discuss in our other post.

The table below shows auto-selected parameters targeting recall 0.97, measured with brute-force search, so the number reflects loss due to quantization alone (64 query clusters, targeting document clusters of size 384, which matches the settings of DiskBBQ).

There are a few things worth highlighting:

• The recall is very sensitive to rerank depth. This is why we nearly always end up choosing the maximum depth available: a step up in rerank depth from 20 to 30 is typically what pushes us to hit the recall target for fewer bits and we prefer fewer bits. In the real system, we tuned this behavior based on a more representative reranking cost.
• Glove underperforms partly we approximate the query distribution with random samples from the corpus, but Glove is also less well characterized by the model than the other datasets. A plausible explanation is that the approximately uniform local density assumption from Section 2 is less reliable for Glove embeddings, which would show up as higher recall variance between queries. However, Glove embeddings are not representative of the actual vectors we need to store.
• The FiQA GTE preconditioning choice is a knife-edge case: preconditioning produced only a tiny expected recall improvement, but the prediction sat right at the recall cutoff and allows us to drop the query from 3 to 2 bits. If we'd rather only keep preconditioning where its benefit is clear-cut, we can enforce a minimum uplift threshold. This sort of fine-tuning of the decision logic leaves all the heavy lifting to estimate recall unaffected.

Key takeaways: auto-tuning vector quantization from first principles

We presented a method to pick optimal quantization parameters to achieve a target recall. It rests on two models that compose cleanly:

1. A geometric model of neighbor distances that follows from a local uniform density assumption. We use this to derive the nearest-neighbor distance, the $N^{-1/d}$ glacial scaling law of the expected distance, and the expected distance profile $R_{(j)} = \alpha(jN_0/N)^{1/d}$. We show that fitting $\alpha$ and $d$ by a simple log-linear regression to average distances in small random samples from the corpus gives an extremely accurate predictive model.
2. A Gaussian quantization error model that is justified by the CLT. Its only parameter $\sigma_b$ is an empirical variance we estimate by comparing quantized and raw vector similarities for a sample of the corpus.

Finally, we show that it is possible to feed the estimated distance model into a Poisson-binomial count of neighbors that intrude on the top-$k$ set. Applying the Lyapunov CLT the expected recall@$k$ after reranking to depth $n$ falls out as a one-dimensional integral we evaluate by quadrature.

The outcome is an accurate ($R^2>0.95$) predictive model of recall as a function of the quantization parameters. Choosing quantization parameters then becomes an ordered search with a predictive model telling us if we’ve hit the recall constraint. And nicely one that also comes with a built-in argument (glacial scaling) for why the chosen parameters remain safe even when estimated from a relatively small fraction of the data.

We’ve built this entire mechanism into Elasticsearch using segment merges as an opportunity to reassess our quantization choices. Aside from the peace of mind this brings (that you’ll achieve good recall whatever vectors you throw at it), it also allows us to chose near optimal parameters from a performance perspective. This closes the loop on our original objective: near optimal performance out of the box, at least as far as quantization goes. We’re pretty excited about the advantages that model based tuning can bring to vector search and look forward to sharing other work we have in this direction in the near future.