Chapter 16: Compression and Index Economics

00-START-HERE · 01-READING-ROUTES · 15_approximate_nearest_neighbor_search · 17_operating_a_vector_store Purpose: Build a defensible retrieval index budget from code length, scoring error, scan shape, and fleet multipliers without confusing a smaller stored vector with a smaller system.

TL;DR

• Quantization changes the stored description of a same-dimensional vector. Dimensionality reduction changes the representation; neither preserves retrieval quality automatically.
• For power-of-two $k$, PQ stores $m\log_2 k$ bits per vector, addresses $k^m$ composite codes and stores $kd$ centroid floats. Codebook capacity is not a recall guarantee.
• Residual IVF-PQ uses the coarse cell address as part of the reconstruction. Its bit-gain estimate is conditional on a high-rate source model, not an accuracy floor. Naive residual ADC builds a table per probed cell; precomputation trades storage for query work.
• Under an unclipped, independent uniform-rounding model, SQ8 has inner-product noise about $4.53\times10^{-4}$ in the worked unit-vector example. A $768$-bit independent-hyperplane code has local cosine-estimator noise about $0.02745$ at cosine $0.8$. These are model-based deviations, not universal ranking-error rates.
• Fast scans combine block layouts, small lookup tables and hardware-specific kernels. Quantizing the lookup table introduces another approximation; scalar and SIMD instruction counts do not determine a speedup by themselves.
• Count identifiers, graph slots, fixed tables, refine storage, rebuild overlap, replicas, payload and metadata separately. Float16 refinement is not exact rescoring of an original float32 corpus.
• A fleet budget must identify where each physical copy resides. Smaller codes do not automatically shrink every RAM, SSD or payload term.

The story

Think of the index as a warehouse that must ship an answer under a strict space and time budget. The original warehouse stores every item as a full $768$-number crate. Each crate takes $3{,}072$ bytes in float32. Ten million crates consume $30.72\,\mathrm{GB}$ before identifiers, graph links, replicas, or source text. Product quantization stops storing whole crates. It divides each crate into $m$ compartments and gives each compartment a catalog number. With $m = 96$ and $k = 256$, each compartment needs one byte. A $3{,}072$-byte crate becomes a $96$-byte catalog slip while still describing all $768$ dimensions. The catalog has enormous reach because every eye, nose, and mouth choice can combine with every other choice. The warehouse can address $k^m$ composite items while storing only $k\times m$ sub-centroids. Since each sub-centroid has width $\frac{d}{m}$, the stored catalog is only $k\times d$ floats. The price is a rigid grid. The catalog cannot place every boundary freely. The IVF level acts like a regional depot. It routes an item to a coarse centroid. Residual encoding catalogs the difference from that address; when the fitted centroids represent the deployed distribution, this can pool a lower-variance source near the origin. That accuracy opportunity is not free or guaranteed: a naive query builds a cell-dependent table for each probed depot, while precomputed terms reduce that work at an explicit memory cost. Scalar quantization rounds shelf measurements to a finer or coarser ruler. The small SQ8 noise calculated here assumes values remain inside the calibrated range and the rounding errors behave as modeled. Binary hashing instead records which side of sampled hyperplanes contains an item. Hamming counts then estimate an angle under the stated random-hyperplane model. Full-vector rescoring can improve the order of the shortlist, but cannot recover a crate that the shortlist missed. The shelving pattern affects how efficiently workers fetch codes. A per-vector layout puts one subquantizer's codes $m$ bytes apart for eight-bit PQ. A block-interleaved layout groups that subquantizer across, for example, $32$ vectors. This supports compact loads and uniform lane work; alignment, unpacking, table precision, tail blocks and the actual kernel still matter. The final invoice includes identifiers, graph slots, centroids, codebooks, optional precomputed tables, rebuild overlap, replicas, refine vectors, source chunks and filtering structures. Compression primarily shrinks the code payload. Index economics carries every remaining term to the right physical copy and storage tier; a separate builder or shared payload store is not free.

Decoder table

Core mechanics

Mathematical conventions

Storage is decimal unless explicitly binary: $1\,\mathrm{kB}=10^3\,\mathrm B$, $1\,\mathrm{GB}=10^9\,\mathrm B$, $1\,\mathrm{KiB}=2^{10}\,\mathrm B$ and $1\,\mathrm{GiB}=2^{30}\,\mathrm B$. Keep intermediate precision and round required integer resources upward. Equal-width PQ assumes $m\mid d$ and fixed-length subcodes; a separately stored sub-index needs $\lceil\log_2 k\rceil$ bits, which equals $\log_2 k$ for the powers of two used here. A multiply-accumulate (MAC) is conventionally two FLOPs; neither is interchangeable with a table lookup or SIMD instruction. Operation-count crossovers are illustrative, not measured latency. Memory-over-bandwidth figures are streaming floors, not $p_{99}$ guarantees. Quantization-noise formulas require their stated bias, clipping and covariance assumptions. Binary binomial formulas below use independent random hyperplanes, not arbitrary coordinate signs. Rescoring is exact only over the fetched candidates, relative to the stored precision and metric; it cannot restore candidates omitted by routing or compressed search. Reported experimental results remain source inputs, not results established by this chapter's arithmetic.

16.1 Product quantization and the $\frac{k^m}{km}$ argument

What

A flat quantizer chooses a nearest centroid from a finite codebook, with a tie rule:

A fixed-length index costs $\lceil\log_2 k\rceil$ bits. Codebook fitting minimizes average squared reconstruction error, for example on a training sample:

Lloyd’s $k$-means algorithm is a local heuristic. The source cites exact Euclidean sum-of-squares clustering as NP-hard even for $k = 2$ in general dimension. A flat $b$-bit code needs $2^b$ centroids. At $b = 32$ and $d = 768$:

Against the modeled ten-million-vector corpus of $30.72\,\mathrm{GB}$, that flat codebook alone is about $429.50$ times larger. A library warning heuristic of $39$ training points per centroid would request:

PQ splits $x$ into $m$ equal contiguous subvectors when $m\mid d$, and fits $k$ sub-centroids per block. Its separately stored fixed-width subcodes have length:

Its representable code count, stored sub-centroid count, and stored coordinates are:

At $d = 768$, $m = 96$, and $k = 256$:

Why

The $m$ factor cancels from codebook memory. Code reach grows exponentially with $m$ while the stored codebook remains $k d$ floats. The vector remains $768$-dimensional. OPQ learns an orthogonal transform $R$, with $R^{\mathsf T}R=I$, before quantizing $Rx$. The rotation preserves Euclidean distances before quantization and can improve how variance and dependence fit the product blocks. It does not guarantee equal block variances or optimal recall. A dense transform stores $768^2\times4=2{,}359{,}296\,\mathrm B$ and costs about $768^2=589{,}824$ MACs per query; training and preprocessing costs should be measured. Already whitened inputs do not prove OPQ is useless.

Failure without it

For the same $32$-bit code, PQ can use $m=4,k=256$. Its codebook uses $768\,\mathrm{KiB}$, while the flat $2^{32}$-centroid alternative uses approximately $13.1941\,\mathrm{TB}$. The $39$-per-centroid heuristic is $9{,}984$ training vectors per subspace, generally reusing the same training vectors across subspaces; it is not a theorem or $m$ disjoint training sets. The analogous flat heuristic is about $1.67504\times10^{11}$ vectors. The flat-to-product codebook-memory ratio at the same $k^m$ representable labels is:

PQ restricts reconstruction cells to products of subspace cells, so their boundaries cannot be placed independently in full space. The very large code count does not prove that all labels are useful or equally likely. Measure recall and reconstruction distortion against the embedding distribution, especially at low rates such as below $0.5$ bits per dimension; that value is a source heuristic, not a mathematical failure threshold.

Cost and complexity

ADC builds:

There are $mk$ entries and $kd$ coordinate accumulations. Direct squared-distance evaluation uses a subtraction, square and accumulation per coordinate; a norm-plus-dot-product implementation has a nominal $kd$ MACs, about $2kd$ FLOPs, plus norm/combination terms. Each candidate needs $m$ table lookups and approximately $m$ additions. These are different work types. For $d=768,m=96,k=256$, the table has $24{,}576$ entries, $98{,}304\,\mathrm B=96\,\mathrm{KiB}$ at float32. The nominal dot-product portion is $196{,}608$ MACs, or $393{,}216$ FLOPs. If one ignores table loads, norm terms, selection and bandwidth, a proxy comparing $2kd+nm$ with $2dn$ gives:

SDC also quantizes the query. It saves no database-code bytes, but can exploit a query code and precomputed symmetric code distances in some workflows. Neither ADC nor SDC has a universal additive positive-bias formula for deterministic centroid quantization; the error algebra and assumptions are given below.

Worked numbers and decisions

• HNSW-Flat with $10^7$ float32 vectors and $M=32$ has $30.72\,\mathrm{GB}$ of vectors plus approximately $2.601290\,\mathrm{GB}$ of allocated link slots under the layer convention below, or $33.321290\,\mathrm{GB}$ before other overhead. Base slots alone are $2.56\,\mathrm{GB}$; this is $64$ four-byte slots per vector, not $32$ eight-byte links.
• PQ96 codes use $960\,\mathrm{MB}$ and the shared codebook $786{,}432\,\mathrm B=768\,\mathrm{KiB}$. The code-payload reduction is exactly $32$ times and the rate is one bit per dimension.
• A query's float32 PQ96 table is $96\,\mathrm{KiB}$. Its nominal dot work is $0.196608$ million MACs, or $0.393216\,\mathrm{MFLOP}$, before other terms.
• Scanning $10{,}000$ codes reads $960{,}000\,\mathrm B=960\,\mathrm{kB}$ of codes. That may fit a particular last-level cache, but does not prove a cache hit, or include the lookup table, IDs and selection state.
• PQ32 codes use $320\,\mathrm{MB}$, $96$ times less code payload than float32, with $2^{256}$ labels and $1/3$ bit per dimension. This is not a $96$-fold reduction of the entire index.
• At the same $96$ bytes, a PCA projection stores $24$ float32 principal coordinates, dropping $744$ principal directions. PQ96 reconstructs all $768$ coordinates approximately. Neither wins independently of the data spectrum and retrieval task.
• An IVF-PQ96 entry adds an eight-byte ID: $104$ bytes and $1.04\,\mathrm{GB}$ of entries, $8.3333\%$ above the code array. Add centroids, codebook, list metadata and optional precomputation separately.
• At $d=128,m=8,k=256$, codes have $64$ bits and the codebook is $128\,\mathrm{KiB}$. A flat $2^{64}$-centroid float32 book would use $9.44473\times10^{21}\,\mathrm B\approx9.44473$ decimal zettabytes.
• The commonly used $k=256$ makes $m$ bytes per code; $m=d/8$ gives one bit per dimension when integral. The listed $d=768$ choices $96$, $64$, $48$, $32$, $24$ and $16$ divide $d$, but are not all its divisors.
• A $k=16$ fast-scan kernel trades smaller subcode alphabets and table quantization against quality; measure it at matched code bytes and recall. OPQ has separate rotation cost.
• Retrain or recalibrate after material encoder or corpus shift. Treat $39k=9{,}984$ samples per subspace as a warning heuristic, not a proven sufficiency guarantee.
• Full float32 vectors can rescore a shortlist exactly in the original metric, but only within that shortlist. Keeping them on NVMe still requires $30.72\,\mathrm{GB}$ of storage plus access, metadata and replication budgets. These budgets distinguish code payload, fixed structures, score error and the physical copies needed for a serving system. A smaller vector description is not automatically a smaller end-to-end deployment.
• HNSW-Flat: The scoped $M=32$ estimate is $30.72\,\mathrm{GB}$ of vectors plus $2.601290\,\mathrm{GB}$ of expected allocated slots, including upper levels. It excludes allocator, label-map and runtime overhead.
• PQ96: The $96$-byte code array is $960\,\mathrm{MB}$; the shared book is $768\,\mathrm{KiB}$. Rate and payload ratios do not establish recall.
• Query table: $96\times256$ float32 entries use $96\,\mathrm{KiB}$. A norm-plus-dot build has a nominal $196{,}608$ MACs, conventionally $393{,}216$ FLOPs, plus remaining terms. The $10{,}000$-code stream is $960\,\mathrm{kB}$.
• PQ32: Codes use $320\,\mathrm{MB}$, $2^{256}$ labels and $1/3$ bit per dimension. Full-index savings are smaller when fixed and per-item non-code terms are counted.
• PCA comparison: $24$ retained principal coordinates cost $96$ bytes; $744$ principal directions are discarded. PQ96 describes all coordinates approximately, not losslessly.
• IVF entries: The ID changes $96$ to $104$ bytes, or $1.04\,\mathrm{GB}$ before fixed terms; the increase over codes is $8.3333\%$. Use hardware measurements rather than byte counts alone to choose $k$ and $m$. A smaller $k=16$ lookup table enables particular shuffle kernels, but table quantization and changed subspaces may alter recall. OPQ adds a transform, and a codebook-trained index must be reevaluated after material distribution shift. The $39$-points-per-centroid heuristic is neither a training lower-bound theorem nor a quality guarantee. Reranking can improve candidate order, but keeping and fetching the original vectors remains a separate storage and latency decision.

16.2 Residual quantization and IVFADC

What

IVF assigns each vector to the nearest of $K_c$ centroids. Residual encoding stores:

Let $X$ denote a random vector and $\mu=\mathbb E[X]$. At a population centroid condition, or for the empirical training distribution at a nonempty-cell Lloyd fixed point:

Then $\mathbb E[X-q_c(X)\mid q_c(X)]=0$, so the cross term vanishes. With $\sigma^2$ denoting finite positive total mean squared deviation, not per-coordinate variance:

Training centroids need not satisfy that identity for a shifted serving population. For a high-rate model with intrinsic dimension $d^*\gt 0$, comparable source shapes and the stated common prefactors, use the schematic approximations:

Equating raw distortion at $R_b+\Delta R_b$ to residual distortion at $R_b$ within this model gives:

For quantizer errors $e_x=\widehat x-x$ and $e_y=\widehat y-y$, the exact ADC and SDC identities are:

Why

The coarse level can remove between-cell variation before PQ encodes residuals. The list address has at most $\log_2 K_c$ bits of information; actual entropy may be smaller for imbalanced assignments. It is implicit in list membership rather than stored in every PQ code, but centroids, IDs and list structures still cost memory. The estimate $\Delta R_b\approx\log_2 K_c$ is not a high-rate lower bound. Different source shapes, cell quality, rates and product-block correlations can change the gain in either direction. Likewise, the often-quoted ADC mean distance $\lVert y-x\rVert^2+\xi$ requires conditionally zero-mean error with $\mathbb E\lVert e_x\rVert^2=\xi$; SDC adds $2\xi$ only with suitable zero means, equal error energy and zero cross covariance. Deterministic centroid errors do not generally satisfy these assumptions. For example, $X\in\{-1,1\}$ equally likely, $\widehat X=0$ and $y=0$ give exact distance $1$ but ADC distance $0$, not $2$.

Failure without it

Without residuals, a shared raw-vector codebook covers the full distribution rather than each centered cell's residual distribution. Residuals can improve that allocation, but do not automatically reduce every query error or improve every rank. When measured $\rho$ is near $1$, centering may offer little distortion benefit while still costing work. The suggested warning $\rho\gt 0.8$ is a workload heuristic, not a theorem. OPQ and centering can interact; measure their joint effect rather than adding their gains.

Cost and complexity

Without precomputation, residual scoring forms $y-c_i$ for each probed cell and builds a cell-dependent table. For balanced or representative probed lists, the following counts use one coordinate accumulation for table work and one addition for scan work; they are not calibrated equal-time operations:

The count-proxy crossover cancels $w$. Using the nominal two-FLOP MAC model instead changes the crossover; ignored loads, norms, table combinations and selection can move it further:

Use $N = 10^{7}$, $d = 768$, $K_c = 4{,}096$, $m = 64$, $k = 256$, and $w = 32$:

• Codes are $64$ bytes and IDs eight bytes: $72$-byte entries use $720\,\mathrm{MB}$.
• Centroids use $12{,}582{,}912\,\mathrm B$ and the book $786{,}432\,\mathrm B$. The scoped total is $733{,}369{,}344\,\mathrm B=733.369344\,\mathrm{MB}$, about $41.8883$ times smaller than float32 vectors alone, before other structures.
• Mean list length is $2{,}441.40625$, so $32$ representative lists contain $78{,}125$ codes; the scan proxy is $5{,}000{,}000$ additions.
• A raw-PQ table has $196{,}608$ coordinate accumulations or nominal MACs. This is $3.93216\%$ of the scan's addition count, but nominal MAC FLOPs are $7.86432\%$; neither ratio is a latency share.
• Naive residual tables use $6{,}291{,}456$ coordinate accumulations, $1.2582912$ times the scan count. The nominal dot-work FLOP ratio is $2.5165824$ before remaining terms.
• The coarse address at $K_c=4{,}096$ contributes at most $12$ label bits. Under the high-rate equal-prefactor model this corresponds to a $12/512=2.34375\%$ code-bit gain, not a guaranteed accuracy gain or floor.

The source's $4\sqrt N$ to $16\sqrt N$ coarse-list starting heuristic gives:

These endpoints are approximately $3.886$ and $15.543$ times the count-proxy crossover, or twice those ratios against the nominal FLOP crossover. The range is a tuning heuristic; it neither guarantees balanced lists nor matched recall. An optional float32 table of cell-dependent residual terms costs:

The exact expansion, including the cell-dependent offset needed when comparing candidates across lists, is:

For PQ64, this optional table uses $268{,}435{,}456\,\mathrm B=268.435456\,\mathrm{MB}=256\,\mathrm{MiB}$ at $K_c=4{,}096$, or $36.6030\%$ of the scoped $733.369344\,\mathrm{MB}$ index before adding it. The combined total becomes $1.0018048\,\mathrm{GB}$. At $K_c=65{,}536$ the table is $4.294967296\,\mathrm{GB}=4\,\mathrm{GiB}$. Precomputed terms remove repeated full-dimensional work, not every query operation: a shared query-dot table still costs nominal $kd$ MACs, cell-table combinations cost $O(wmk)$, and list scans, coarse search and selection remain.

Worked numbers and decisions

• Compare raw PQ, residual PQ and precomputed residual PQ at matched code bytes, recall, load and memory. Disable or alter residual encoding when the measured benefit does not justify its real query and storage cost; $\rho\gt 0.8$ or a half-scan build share are heuristics to test, not universal thresholds.
• ADC keeps the original query; SDC may be useful for already coded queries. Additive positive-distance bias is not a general guarantee for either method.
• At $K_c=65{,}536,w=32$, mean scan work is $312{,}500$ additions while naive residual build work stays $6{,}291{,}456$ nominal MACs: a count ratio $20.1326592$, or nominal dot-work FLOP ratio $40.2653184$.
• The balanced scanned corpus fraction is $0.78125\%$ at $4{,}096$ cells and $0.048828125\%$ at $65{,}536$. Restoring that fraction takes $w=512$, not a promise of restored recall.
• At $w=512$, scan work returns to $5{,}000{,}000$ additions but table work rises to $100{,}663{,}296$ nominal MACs. The same large build-to-scan ratio remains. Benchmark precomputation, another coarse routing strategy or raw PQ rather than assuming one remedy always wins.
• Rerank a measured shortlist when original vectors are available. Exact float32 candidate scoring is not global exact search; increasing code bits and increasing candidate coverage address different failure modes.

16.3 Scalar and binary quantization

What

Float32 payload is $4d$ bytes, or $3{,}072$ bytes at $d=768$. For $b\ge1$ bits and a calibrated range $\beta_j\gt \alpha_j$, a clipped nearest-level scalar quantizer is:

For $x_j\in[\alpha_j,\beta_j]$, nearest rounding gives $\lvert e_j\rvert\le\Delta_j/2$, where $e_j=\widehat x_j-x_j$. Clipped outliers need not obey that bound. A zero-mean uniform-bin approximation gives:

A unit vector has average squared coordinate $1/d$. If the unit-vector distribution is also zero-mean and isotropic, each coordinate has the following RMS/standard-deviation scale; it is not the value of every coordinate:

With $[\alpha,\beta]=[-0.2,0.2]$ and $b = 8$:

For a fixed exact unit query, the score below is the dot product with the reconstructed vector, without renormalizing that reconstruction. With error mean $\mu_e$ and covariance $\Sigma_e$:

Only under $\mu_e=0$, $\Sigma_e=\sigma_e^2I$ and $\lVert q\rVert=1$ does score deviation equal $\sigma_e$. Per-dimension ranges, correlated errors, clipping and renormalization change that result. For binary hashing, let $n_b$ independent isotropic random hyperplanes encode a nonzero vector by $\mathop{\mathrm{sign}}\nolimits(a_\ell^{\mathsf T}x)$. For a fixed pair at angle $\theta$:

The source connects the single-random-hyperplane collision result to SimHash through Goemans and Williamson (1995) and Charikar (2002). Raw coordinate signs have no such guarantee for arbitrary fixed embeddings. A random orthogonal rotation has dependent hyperplane directions, so it does not by itself establish the binomial variance; learned ITQ also requires empirical error calibration.

Why

SQ8 reduces precision while retaining approximate component values. Binary Hamming counts estimate angular similarity under an appropriate hashing model instead of using one-bit reconstructed components. XOR and population count make Hamming scoring cheap, but query hashing, memory traffic, selection and candidate recall still cost work. A cosine estimate from Hamming is nonlinear and is generally biased even when the angle estimate is unbiased.

Failure without it

For finite, normal-range values rounded to nearest, float16 has $11$ significand bits and the usual relative error bound:

Subnormals, overflow and the actual rounding implementation need separate treatment. At component RMS $1/\sqrt{768}$, the normal-range absolute bound scale is about $1.762\times10^{-5}$. A further uniform-relative-rounding approximation gives RMS near $1.0173\times10^{-5}$, about $44.5$ times below the SQ8 component-noise model while using twice the bytes. This does not prove a score-error rate or universal ranking gap. Extrapolating the uniform-bin scalar model to one bit gives $\Delta=0.4$ and $\sigma_e\approx0.11547$, but the high-rate approximation is especially questionable when unit-vector coordinates cluster near zero. Treat it as a surrogate, not a measured cosine deviation. Independent random-hyperplane hashing changes the estimator; an arbitrary coordinate-sign code or learned/orthogonal rotation must have its own bias, variance and recall measured. No theorem requires every binary deployment to rerank, but cosine-quality requirements may make it necessary.

Cost and complexity

At cosine $0.80$:

The delta-method cosine deviation is $\sin\theta\,\mathop{\mathrm{sd}}\nolimits(\widehat\theta)\approx0.0274504$ at cosine $0.8$ and $n_b=768$. It is not an exact standard deviation or a universal error bound. Binary code payload is eight times smaller than SQ8 and its local modeled deviation is about $60.62$ times larger. Comparing it with the extrapolated one-bit scalar deviation gives a ratio near $4.21$, but does not validate that scalar noise model. For $10^7$ vectors and a sustained code-stream bandwidth of $50\,\mathrm{GB/s}$, the following are payload-only read floors, not measured end-to-end scans:

Two float32 calibration endpoints per coordinate use $2(768)(4)=6{,}144\,\mathrm B$. For two item scores, independent SQ8 errors in the stated isotropic model give a difference deviation:

The $78$-deviation number is a scale comparison, not a justified Gaussian tail estimate. There is a stronger statement for this particular unclipped equal-step raw-dot model: $\lvert q^{\mathsf T}(e_1-e_2)\rvert\le\Delta\lVert q\rVert_1\le\Delta\sqrt{768}\approx0.04347\lt 0.05$, so a $0.05$ gap cannot flip under those bounds. Clipping, non-unit queries, other scoring rules or changed ranges invalidate that conclusion. For binary scores, an independent, equal-local-variance Gaussian surrogate at cosine $0.8$ gives the illustrative calculation below. The real scores share hash planes and a query, so their errors need not be independent:

For shared independent planes, even the covariance depends on a third angle. Write $p_a=\theta(q,x_a)/\pi$, $p_b=\theta(q,x_b)/\pi$ and $p_{ab}=\theta(x_a,x_b)/\pi$. One-bit disagreement covariance is $(p_a+p_b-p_{ab})/2-p_ap_b$, and $\mathop{\mathrm{Cov}}\nolimits(\widehat\theta_a,\widehat\theta_b)$ is $\pi^2/n_b$ times that quantity. Thus a score gap alone does not determine a binary flip rate. For a separate reranking budget, fetching $200$ original float32 vectors needs:

Assume every candidate needs one independent read, all requests are ready, maximum concurrency is $32$ and every service time is exactly $100\,\mathrm{\mu s}$. Full waves then need:

That is $3.64583\%$ of the binary $19.2\,\mathrm{ms}$ read floor, not a measured fraction of end-to-end latency. A fluid throughput calculation gives $0.625\,\mathrm{ms}$, but cannot complete a partial final wave in the equal-service-time model. If each vector is read as one aligned $4\,\mathrm{KiB}$ record, device traffic is $819.2\,\mathrm{kB}$ rather than $614.4\,\mathrm{kB}$. Queueing, page crossings, cache hits, selection and rescoring compute change actual latency.

Worked numbers and decisions

• PQ96 and $768$-bit binary codes both have $96$ bytes and $2^{768}$ labels; their reconstruction geometry and estimators differ. Equal code count does not imply equal quality.
• Per-dimension clipping at the $0.1\%$ and $99.9\%$ quantiles is a calibration heuristic. It permits outliers beyond the half-step rounding bound. If every coordinate has exactly $0.2\%$ marginal clipping probability, expected clipped coordinates at $d=768$ are $1.536$; under further coordinate independence, about $78.51\%$ of vectors have at least one clipped coordinate. Production drift can change both rates.
• Distinguish raw coordinate signs, independent random projections, orthogonal rotations and learned ITQ. Only the stated independent-hyperplane construction directly gives the binomial formula; rotations and learned codes need measured covariance and recall.
• The source names library scalar options such as QT_8bit and QT_8bit_uniform. Doubling an otherwise fixed range doubles the step and quadruples uniform-bin MSE; it may also change clipping error, so total MSE need not quadruple.
• Oversampling by $3$ to $5$ times and rescoring are starting heuristics. Measure candidate recall as well as final ranking; rescoring cannot recover excluded items. A sub-$5\,\mathrm{ms}$ budget is not by itself a reason to accept unmeasured error.
• Independent dense $768$-plane query hashing costs $768^2=589{,}824$ MACs before the binary scan; no learned codebook does not mean free encoding or rebuilding. Structured and learned transforms have different costs.
• Truncating a suitably trained Matryoshka representation to $256$ dimensions and storing $256$ sign bits uses $32$ bytes, $96$ times less payload than original $768$-dimensional float32. Ablate truncation and binarization separately, with an explicit sign-code model and measured recall.

16.4 FAISS, parallelism, and why block structure matters

What

PQ ADC computes:

Building the table touches $kd$ coordinates; a norm-plus-dot implementation has nominal $kd$ MACs plus other terms. Scanning one code uses $m$ lookups and $m-1$ additions, or $m$ additions with a zero-initialized accumulator. Loads, arithmetic and vector instructions are distinct costs. An illustrative coordinate-accumulation versus lookup-and-add count proxy, not an instruction- or time-equivalent comparison, gives at $d=768,k=256,m=16$:

A conventional eight-bit PQ row stores a vector's $m$ subcodes together. Across $32$ vectors, one fixed subquantizer is then sampled at stride $m$ bytes. Implementations can still vectorize or cache such gathers; the layout does not uniquely fix instruction count. A fast-scan kernel stores subcodes in blocks, for example $32$ vectors with subquantizer-major order. Four-bit subcodes are packed and unpacked for register lookup. A vpshufb-style byte shuffle addresses $16$ entries within each $128$-bit lane; wider vector units replicate or arrange tables by lane. Quantizing table entries to bytes is an additional approximation, and accumulation width, offsets and saturation handling must be specified. Choosing $k=16$ alone does not make a float32 table byte-sized. At the same $128$-bit budget:

Why

Within a full block, PQ scoring has regular logical work and can avoid graph-like pointer traversal. A $32$-vector block can suit a $32$-thread NVIDIA-style warp, but CPU fast-scan layouts and GPU warp kernels are not the same implementation. Tail blocks, stalls, coarse routing and top-$k$ selection can still leave lanes idle. Uniform code work is an opportunity for utilization, not a guarantee of $100\%$ occupancy. Register-resident top-$k$ selection can avoid materializing every score and sorting it in global memory. A comparison baseline should say whether it materializes all scores, uses a heap, or uses another streaming selection method.

Failure without it

The source's opening example compares $307.2\,\mathrm{GB}$ of float32 payload with $1.6\,\mathrm{GB}$ of $128$-bit PQ codes, a $192$-fold code-payload reduction, while reporting only about a twofold scan improvement. Codebook lookups, arithmetic and selection can replace bandwidth as the bottleneck. A $16\,\mathrm{KiB}$ float32 query table is half of a stipulated $32\,\mathrm{KiB}$ L1 cache, not proof of a particular miss rate or a universal speedup. The worked selected-code stream is about $390.6\,\mathrm{kB}$ per query. A single unbatched query may underfill an accelerator, but that depends on kernel, coarse work, concurrency and hardware; bytes alone do not prove underutilization. HNSW traversal has dependent accesses and uneven candidate work, which can make naive lane mappings inefficient. The source's FAISS GPU-HNSW statement applies to its reported implementation/version, not a theorem that graph search cannot run on GPUs. Specialized graph kernels such as the source's CAGRA example use regularized layouts and degree budgets to improve parallelism; fixed out-degree alone does not prove full utilization.

Cost and complexity

The source reports a four-bit block scan about $4$ to $6$ times faster than its conventional baseline, and reports WarpSelect at $8.5$ times a prior implementation plus a billion-vector $k$-NN graph built in under $12$ hours on four Maxwell Titan X GPUs. Preserve the respective study, workload and baseline scopes; these are not predictions for the arithmetic example below or current hardware. Use $N = 10^{8}$, $d = 768$, $\mathrm{nlist} = 262{,}144$, and $\mathrm{nprobe} = 64$:

PQ8 with $m = 16$ and $k = 256$:

• PQ8 with $m=16$ stores $16$-byte codes: $1.6\,\mathrm{GB}$ versus $307.2\,\mathrm{GB}$ of float32 payload, a $192$-fold code-payload reduction.
• Use $n_c=24{,}414$ only as a rounded planning count. Its code stream is $390{,}624\,\mathrm B=390.624\,\mathrm{kB}$.
• A nominal scalar accounting of $16$ subcode extractions, $16$ table loads and $15$ additions is $47$ operations per code, or $1{,}147{,}458$ across the planned candidates. This is not a count of CPU micro-operations or cycles.
• The nominal $196{,}608$-coordinate table build corresponds to $12{,}288$ candidates under the earlier heterogeneous count proxy, $50.331648\%$ of the mean candidate count. The percentage is not a measured runtime share.
• The full index also has $0.8\,\mathrm{GB}$ of eight-byte IDs, $0.805306368\,\mathrm{GB}$ of coarse centroids and a $0.000786432\,\mathrm{GB}$ book: a scoped $3.2060928\,\mathrm{GB}$ before other terms. Coarse routing over $262{,}144$ centroids must be budgeted, not hidden in the selected-code scan. PQ4 with $m = 32$ and $k = 16$:
• PQ4 with $m=32,k=16$ retains the same $128$ bits and $1.6\,\mathrm{GB}$ code payload; changed subspaces and LUT precision can change recall.
• If the $24{,}414$ planned candidates form one packed run, $\lceil24{,}414/32\rceil=763$ blocks contain $24{,}416$ slots. Real IVF lists generally round blocks separately, so the sum of list block counts can be larger.
• Under a particular kernel's assumed seven vector instructions per subquantizer per block—one load, two nibble unpacks, two shuffles and two accumulation operations—the illustration is:

The numerical ratio $1{,}147{,}458/170{,}912\approx6.71374$ compares scalar logical operations with vector instructions, not equivalent work or a predicted speedup. Extra packing, table conversion, accumulation overflow handling, routing and selection are omitted. For the smaller codebooks, the table-work count proxy becomes:

The proxy ratio is $384/24{,}414.0625=1.572864\%$, not a measured table-build share. Comparing it with the $50.331648\%$ PQ8 proxy does not account for the different scan kernels. If all planned candidate scores are materialized as float32, their output size is:

One write plus one reread is $195.312\,\mathrm{kB}$, exactly $50\%$ of the $390.624\,\mathrm{kB}$ code stream. This is traffic accounting, not a $50\%$ latency penalty; streaming selection may avoid those transfers and caches can change the path. The reported $4$-to-$6$-fold kernel speedup cannot be inferred from, or disproved by, the $6.71374$ unlike-instruction-count ratio. Establishing why a measured gap occurs requires matched baselines, hardware counters and end-to-end timing; unchanged traffic and selection are plausible contributors, not conclusions proved by this ratio. For residual IVFADC at these PQ8 settings, a precomputed table costs:

This optional table is $2.68435456$ times the $1.6\,\mathrm{GB}$ code array, before the separate IDs, centroids, codebook and overhead. The PQ4 $m=32,k=16$ version would have a different table budget, $536.870912\,\mathrm{MB}$; kernel and library support must also be checked.

Worked numbers and decisions

• Compare a supported fast-scan implementation with classic IVF-PQ at the same total code bytes and measured recall; do not assume the smaller LUT is accuracy-free or always faster.
• The $12{,}288$-candidate PQ8 and $384$-candidate PQ4 figures are count proxies, not universal latency break-evens. Include coarse routing and any per-cell residual work.
• Select CPU, GPU, graph or scan kernels from measured workload shape. Batch queries when useful, but include batch-fill delay for interactive requests.
• A tuned CPU can beat an underfilled accelerator, while a specialized GPU graph can beat naive CPU/GPU defaults. Neither is a universal rule.
• Budget residual precomputation explicitly and use measured query savings to decide whether it is worthwhile. The suggested $2^{16}$-centroid caution is configuration-dependent, not a hard library or mathematical limit.

16.5 Index memory arithmetic, end to end

What

At $d = 768$:

IVF entries in these examples add an eight-byte ID. The HNSW example assumes implicit positional labels and four-byte neighbor IDs; stable external keys, deletion state and label maps can add bytes. Turn terms off when the corresponding structure is absent rather than adding IVF and graph terms indiscriminately. HNSW levels follow:

For an integer layer $j\ge0$, $\Pr(\ell\ge j)=M^{-j}$. Under the stated allocation convention, base layer zero reserves $2M$ four-byte neighbor slots and each occupied upper layer reserves $M$. Actual populated degree is not the same as reserved capacity, and implementations may allocate differently. The expected allocated slot bytes per node, excluding counts, pointers, alignment and other overhead, are: