ScaNN

Not all quantization error is equally bad

Each quantiser on the last pages cuts squared reconstruction error: put the centroids where they make ‖q(x) − x‖² as small as doable, summed over the corpus. That objective treats each way of error as equally harmful.

For max dot dot search it is not. Here is the input, and it is short enough to hold in your head.

Take a stored vector x and its quantised version q(x). Split the residual r = q(x) − x into a part with x and a part perpendicular to it:

r = r∥ + r⊥

Now ask what each does to the dot dot with a query. The queries that matter for x — the ones where getting x's score right decides whether it is gave at all — are the ones roughly *aligned* with x. That is what "scores highly under dot dot" means.

For a query aligned with x, the parallel part r∥ adds or subtracts almost right from the score. The perpendicular part r⊥ projects onto that query just weakly, and across the set of such queries it points in in effect arbitrary ways and averages toward zero.

So the two parts have quite else effects on the thing you care about, and an objective that weights them equally is optimising the wrong quantity.

The loss, and the slider

Anisotropic vector quantization weights them else:

loss = η · ‖r∥‖²  +  ‖r⊥‖²        with η > 1

η is the slider. At η = 1 this is ordinary squared error and the assignment is the same to plain k-means — the readout confirms zero vectors changed centroid. That is the control condition, and it is worth setting first so you can see that the machinery does nothing until you ask it to.

Raise η and vectors start choosing else centroids: the blue ones. They are accepting a more *total* error in exchange for a less error with their own way — a bad trade under the usual objective and a good one under this one.

The paper derives η from a target: if you care about vectors whose dot dot exceeds some threshold, that threshold implies a weight. In practice it is tuned, and the useful range is small — the gain here peaks around 2 to 3 and shrinks by 6, since weighting the parallel error too heavily starts ignoring perpendicular error that does still matter.

Why the average is the measurement

The readout shows two recall figures for the query you are dragging and the two averaged bars, and the single-query pair trade places constantly.

That is not noise in the case. It is the nature of the claim. Anisotropic quantisation does not promise a better answer for a *given* query. It promises a better expected answer over the distribution of queries for which a vector would be a top yield. A case that showed one query and declared victory would be gauging a thing the way never claimed.

So the bars here are MIPS recall@k averaged over 48 fixed queries, computed by running both assignments against an right dot-dot answer. The anisotropic bar is always ahead in the middle of the η range, and the gap is a few points — which is the size of effect the paper reports, and the size worth having when it costs nothing at query time.

The rest of the system

Anisotropic quantisation is the novel part. ScaNN as shipped is three stages and the else two are standard, which is worth knowing since the benchmark counts belong to the whole pipeline.

Partition. A learned tree over the dataset restricts the search to a fraction of the leaves. This is IVF's role and it does IVF's job.

Score. Anisotropic quantisation with short codes, scored with SIMD in-register lookups rather than memory-resident tables — the implementation detail that makes the scan fast enough to matter. Aggressively lossy on purpose.

Rescore. Take the top few hundred and recompute right dot products from the full vectors.

That last stage is why the middle one can afford to be so lossy. And it is the same input as IVF-PQ's rerank: a cheap stage just has to give a good candidate *set*, and an right stage over a few hundred vectors fixes the sorting. Set the rescoring slider to zero here and both recall figures fall together — which tells you that a good part of ScaNN's benchmark spot is the rescoring, not the quantiser.

When the input applies, and when it evaporates

ScaNN leads the ann-benchmarks glove-100-angular leaderboard and is the right choice when the workload really is max dot dot search: recommendation scoring, two-tower retrieval, dot dot against unnormalised embeddings.

There is an key caveat. If your vectors are L2-normalised, the anisotropy input mostly evaporates. With each vector the same length, dot dot, cosine and Euclidean ranking all coincide, and the parallel way stops being special in the way the derivation needs. Many embedding nets normalise by default — sentence-transformers does, OpenAI's embeddings arrive normalised — so this is worth checking before choosing an index on the strength of this yield.

The real drawbacks are ecosystem rather than coded: ScaNN is a library rather than a store, tied to TensorFlow, with fewer integrations than HNSW. That is why it appears less much in vector store backends than its benchmark spot suggests it should.

import scann

# Vectors NOT normalised: the anisotropy argument needs varying magnitudes.
searcher = (
    scann.scann_ops_pybind.builder(dataset, 10, "dot_product")
    .tree(num_leaves=2000, num_leaves_to_search=100, training_sample_size=250_000)
    .score_ah(2, anisotropic_quantization_threshold=0.2)   # the eta of this page
    .reorder(100)                                          # exact rescoring
    .build()
)

neighbors, distances = searcher.search_batched(queries)

Three lines, three stages. num_leaves_to_search is IVF's nprobe under one more name; anisotropic_quantization_threshold is the parameter this whole page is about; reorder(100) is the rescoring shortlist. Cutting the .reorder call is the single change that most degrades the yield, which is the same lesson as the IVF-PQ page from a else way.

What to check before choosing it

Two measurements decide whether any of this applies to your workload, and both take minutes.

Are your vectors really varying in length? Compute the norms and look at the spread. If they are all 1.0 — which they are if you used sentence-transformers with its default, or OpenAI's embedding end — the anisotropy derivation has nothing to work with, since the parallel way is just special when size carries data. Dot dot, cosine and Euclidean rankings all coincide there, and a plain quantiser is doing the same job for less trouble.

Is your ranking truly max dot dot? Two-tower retrieval scoring unnormalised thing vectors is. Semantic search over normalised sentence embeddings is not, still when the library calls the metric dot_product.

If both answers are yes, the left thing to get right is the baseline. ScaNN's benchmark spot belongs to a three-stage pipeline — partition, lossy quantised scoring, right rescoring — so the honest check is IVF-PQ with its refinement stage, which has the same shape. Checking against plain HNSW, which rescores nothing, credits the quantiser with the rescoring pass. That is the same confusion the rescoring slider on this page exists to expose.

And if both answers are no, the idea is still worth having. Decomposing quantisation error into a part that moves the score and one that mostly does not is the transferable part, and the question it poses — which errors is my ranking really sensitive to? — recurs wherever a cheap estimate feeds an sorting.

In one line

ScaNN quantises with a loss that weights error with a vector's own way more heavily than error across it, since that is the part that distorts dot products for the queries that would have ranked the vector highly. Same code length, better MIPS recall — measured over a workload, not a query. The full system is partition, quantised scoring, then right rescoring, and the last stage is what lets the middle one be so lossy.

Questions people ask

What does η really change? Which centroid each vector is given to, and nothing else. At η = 1 the assignment is the same to plain k-means. Raise it and vectors begin accepting a more *total* error in exchange for a less error with their own way. The useful range is narrow — the gain peaks around 2 to 3 and shrinks by 6,. This is since weighting the parallel error too heavily starts ignoring perpendicular error that does still matter.

Why does a single query sometimes get worse? Since the claim is about an hope, not a query. Anisotropic quantisation promises a better expected answer over the distribution of queries for which a vector would be a top yield. A case that showed one query and declared victory would be gauging a thing the way never claimed.

Does it help if my embeddings are normalised? Mostly no. And it is the first thing to check. With each vector the same length, dot dot, cosine and Euclidean ranking coincide and the parallel way stops being special in the way the derivation needs.

How much of the benchmark yield is the quantiser? Not all of it. And not most of it. ScaNN as shipped is partition, quantised scoring, then right rescoring of a few hundred candidates. And cutting .reorder() degrades the yield more than any η setting does.

What is the fair baseline? IVF-PQ with refinement, since it is the same three-stage shape. Benchmarking a rescoring pipeline against a non-rescoring one attributes the rescoring to the quantiser.

Why is it less common in vector stores than its benchmark spot suggests? Ecosystem. Rather than algorithm: it is a library. Rather than a store, tied to TensorFlow, with fewer integrations than HNSW. The algorithm is not what is holding it back.

Recap in one screen

• Squared reconstruction error treats each way of error as equally harmful. For max dot dot search it is not.
• Split the residual into parts parallel and perpendicular to the stored vector. For the queries that would rank that vector highly. Those roughly aligned with it. The parallel part moves the score almost right while the perpendicular part averages toward zero.
• The loss weights them η : 1 with η > 1. At η = 1 it is just k-means, which is the control condition worth setting first.
• The payoff is a few points of MIPS recall at the same code length, measured over a workload rather than a query.
• The shipped system is three stages: learned partition, anisotropic quantised scoring with in-register SIMD lookups, then right rescoring. The last is what lets the middle one be so lossy.
• If your vectors are L2-normalised the input mostly evaporates. Check the norms before choosing an index on the strength of this yield.