ScaNN (Scalable Nearest Neighbors) is Google’s answer to a very specific question: when you compress a billion vectors so they fit in memory and can be scored fast, which quantization error should you try to remove? Ordinary product quantization removes the error that makes the reconstructed vector look most like the original — it minimizes squared distance, treating every direction of error as equally bad. ScaNN’s insight is that for maximum inner-product search (MIPS), the thing you actually care about is the score <q, x>, and quantization error along the direction of the datapoint corrupts that score far more than error orthogonal to it. Weighting the loss to punish the parallel error — anisotropic, score-aware quantization — recovers noticeably higher recall at the same compute. This piece derives that intuition, gives the loss, and walks the partition → quantized-scoring → exact-rescoring pipeline that makes ScaNN fast.

MIPS: the problem ScaNN is built for

Retrieval-augmented generation, recommendation, and embedding search all reduce to the same primitive: given a query vector q and a database of vectors x_1 … x_N (each of dimension d), find the few x_i that maximize the inner product <q, x_i>. That is maximum inner-product search, and unlike nearest-neighbor in Euclidean distance it is not symmetric or metric — the winner is the vector most aligned-and-long in the query’s direction, not the closest one.

Brute force is O(N · d) multiply-adds per query: for N = 10^9, d = 128 that is ~10^11 operations — hopeless at scale. Every practical system therefore prunes (look at only a slice of the database) and compresses (score cheap approximations, not full vectors). ScaNN designs both, but its signature contribution is the compression step: a quantizer trained to preserve the score rather than the vector. Everything below builds from that distinction.

Advertisement

Score error lives in the residual

Replace each datapoint x with a quantized stand-in x̃ (a codeword). Define the residual r = x − x̃ — what quantization threw away. The quantity you actually harm is the score, and the score error for a query q is beautifully simple:

<q, x> − <q, x̃>  =  <q, x − x̃>  =  <q, r>

So the error is the query’s inner product with the residual — the hinge of the whole method. The damage a residual does is not ||r|| on its own; it is how much of r the query ‘sees.’ A residual pointing where retrieving queries care is expensive; one pointing elsewhere is nearly free. Plain quantizers ignore this and shrink ||r|| uniformly. ScaNN asks a sharper question: of all residuals with a fixed squared length, which orientation does least damage to the scores of the queries that would actually retrieve this point?

Why plain PQ optimizes the wrong thing

Product quantization (PQ), the workhorse behind FAISS-style indexes, splits each vector into M sub-vectors and runs k-means in each subspace, so a point becomes M small codebook indices (typically M bytes). k-means minimizes squared reconstruction error ||x − x̃||^2 = ||r||^2. That objective is isotropic: it treats an error of size ε the same no matter which way it points, because Euclidean distance has no preferred direction.

But MIPS does have a preferred direction — the datapoint’s own — because the queries that retrieve x point roughly toward it. Minimizing ||r||^2 spends the bit budget equally on error components that matter a lot and ones that barely matter, so a reconstruction-optimal codeword is not a score-optimal one. ScaNN keeps PQ’s data structure — subspaces, codebooks, byte codes, fast table lookups — but swaps the training objective. Same machinery, different loss, materially better MIPS recall.

The anisotropic insight: parallel vs orthogonal residual

Decompose the residual into the part along the datapoint and the part perpendicular to it:

r_∥ = ( <r, x> / ||x||^2 ) · x      (parallel: along x)
r_⊥ = r − r_∥                        (orthogonal: perpendicular to x)

Here is the geometry. A query that ranks x highly points close to x’s direction. The parallel residual r_∥ lengthens or shortens x along that very direction, shifting the score of every such query the same way — a systematic bias that does not cancel. The orthogonal residual r_⊥ points sideways; across the cone of queries that retrieve x, its contribution <q, r_⊥> is sometimes positive, sometimes negative, and averages toward zero. Same ||r||, wildly different score impact — so the quantizer should push its error sideways, preferring a mostly-orthogonal residual even if that worsens plain reconstruction distance slightly.

A worked example

Take x = (1, 0) in 2-D and a query q = (1, 0) that points straight at it, so the true score is <q, x> = 1. Give two candidate codewords the same residual length ||r|| = 0.1, one parallel and one orthogonal:

parallel   error:  x̃_A = (0.9,  0.0)   r = (0.1, 0.0)
orthogonal error:  x̃_B = (1.0, −0.1)   r = (0.0, 0.1)

score with x̃_A:  <q, x̃_A> = 0.9   → error = 0.1
score with x̃_B:  <q, x̃_B> = 1.0   → error = 0.0

Identical reconstruction MSE, yet the orthogonal codeword gives zero score error while the parallel one loses the full 0.1. A slightly off-axis query q = (0.98, 0.20) sees a small error from the orthogonal codeword (−0.02) but still near-full error from the parallel one. Averaged over the cone of retrieving queries, orthogonal error is cheap and parallel error is dear — yet plain k-means, blind to this, calls x̃_A and x̃_B equally good.

The score-aware (anisotropic) loss

ScaNN turns the intuition into an objective. Instead of ||r||^2 = ||r_∥||^2 + ||r_⊥||^2, it minimizes a weighted sum:

L(x̃) = h_∥ · ||r_∥||^2  +  h_⊥ · ||r_⊥||^2 ,   with  h_∥ ≥ h_⊥

The weights come from a real derivation. Take the expected squared score error E_q[ <q, r>^2 ] over a query distribution and — crucially — weight it toward queries with large <q, x> (the ones for which x is a genuine candidate); the expectation separates into exactly these two terms. For queries uniform on the sphere the ratio grows with both the dimension d and the emphasis on high-scoring pairs: the harder you weight toward large inner products, the more the parallel component dominates. Set h_∥ = h_⊥ and the loss collapses to ordinary MSE — PQ is just the isotropic special case. Turn the ratio up and you get score-aware quantization.

Advertisement

Quantized scoring with lookup tables

With codebooks trained under the anisotropic loss, scoring uses the same fast trick as PQ — asymmetric distance computation. Split q into the same M sub-vectors; for each subspace, precompute a small lookup table of the inner product between q’s sub-vector and each codeword:

build tables:   M × k dot products of size d/M   ≈  k · d  ops per query
score a point: <q, x̃> ≈ Σ_m  table_m[ code_m(x) ]   =  M table lookups + adds

The query keeps full precision; only the database is quantized — hence asymmetric. Scoring a candidate costs M table reads and adds instead of d multiply-adds. ScaNN pushes this further with 4-bit codes (k = 16) whose tables fit in SIMD registers, scoring many points per vector instruction — the reason ScaNN is fast on commodity CPUs, not just accelerators.

The tree: partitioning to prune

Cheap per-point scoring still can’t touch a billion points per query, so ScaNN prunes first with a partitioning tree. A coarse k-means carves the dataset into K partitions, each with a centroid. At query time you score the K centroids, keep the top w partitions, and quantize-score only the points inside them — roughly w · N / K candidates instead of N.

ScaNN’s tree is MIPS-aware: the partitioning is trained with the same score-aware objective, so assignments respect inner product rather than raw distance. The knob w is the recall/latency dial — probe more partitions and you catch more true top-k vectors at higher cost. This is the same inverted-file idea as classic IVF, tuned so the pruning step doesn’t silently discard the vectors the anisotropic scorer was built to rank.

Rescoring the top candidates exactly

Quantized scores are approximate — good enough to rank a shortlist, not to settle the final order. So ScaNN ends with a rescoring pass: take the top N' candidates by approximate score, fetch their full-precision vectors, compute the exact inner product <q, x_i>, re-rank, and return the top k.

The cost is O(N' · d), and because N' is tiny next to N, this exactness is nearly free while erasing most of the quantization’s ranking mistakes — the classic approximate-then-verify pattern: a fast, lossy filter proposes; a slow, exact check disposes. The anisotropic loss earns its keep here — by preserving score rather than shape, the approximate stage puts more of the true top vectors into the shortlist, so a smaller N' suffices for the same recall.

The pipeline end to end

Stack the three stages and trace one query. Partition: score K centroids, probe the top w, narrowing a billion points to perhaps a hundred thousand. Quantized-score: for those candidates, sum M table lookups each — additions, SIMD-parallel — and keep the top N' ≈ 10^3. Rescore: exact d-dimensional inner products on those N', then return the top k.

Against brute force’s N · d ≈ 10^9 × 128 ≈ 10^11 multiply-adds, the three stages total roughly K · d + candidates · M + N' · d — with K and N' in the thousands and M ≪ d, that is millions of ops, three to four orders of magnitude cheaper. The anisotropic loss is what keeps the aggressive middle stage accurate enough that the cheap path still returns the right answers.

Practical notes, CPU-SLM fit, and pitfalls

ScaNN is a natural retrieval backend for a CPU-hosted small language model: RAG needs a top-k embedding lookup on every query, and ScaNN’s in-register 4-bit lookup tables make that lookup fast without a GPU, so higher recall at fixed compute translates directly into cheaper, better-grounded generation. A few cautions. The anisotropic weight ratio (its threshold hyperparameter) is a real dial — too isotropic and you leave recall on the table, too aggressive and you overfit the parallel direction; tune it on held-out queries.

The premise is inner product: L2-normalize every embedding and all norms become 1, MIPS collapses toward cosine nearest-neighbor, and the anisotropic edge shrinks — the method pays off most when vector norms genuinely vary. Finally, don’t starve the tail: an N' set too small caps recall however good the quantizer, and too few probed partitions w discards winners before scoring sees them. Balanced, ScaNN turns billion-scale MIPS into a millisecond, cache-friendly operation — by quantizing for the score, not the shape.

ScaNN accelerates maximum inner-product search by quantizing for the score instead of the shape. The score error of a quantized point is <q, r>, the query’s inner product with the residual — so error parallel to the datapoint (which biases every retrieving query the same way) hurts far more than orthogonal error (which averages toward zero). ScaNN’s anisotropic loss h_∥||r_∥||^2 + h_⊥||r_⊥||^2 with h_∥ ≥ h_⊥ encodes exactly that, and plain product quantization is just the isotropic h_∥ = h_⊥ special case that optimizes reconstruction, not ranking. Wrapped in a partition → quantized-scoring → exact-rescoring pipeline — prune with a tree, score candidates with SIMD lookup tables, verify the shortlist exactly — it makes billion-scale MIPS fast on a CPU while keeping the vectors that matter.