Chapter 21: Learned Sparse and Multi-Vector Retrieval

00-START-HERE · 01-READING-ROUTES · 20_dense_retrieval · 22_reranking This chapter prepares you to explain how learned lexical weights, token-level matching, compression, pruning, and rank fusion trade retrieval quality against index size and latency.

TL;DR

• BM25 and SPLADE can be expressed as sparse dot products. SPLADE learns nonnegative weights over vocabulary pieces, including absent pieces; support does not guarantee literal containment or relevance.
• ReLU supplies exact zeros. The logarithm compresses large positive logits but is unbounded and does not cap repeated contributions under sum pooling.
• FLOPS regularization penalizes squared batch-mean weights. It can encourage balanced activation, but mean weights are not probabilities. A feasible capped-Zipf example at $160$ average nonzeros gives a $5.910484$-fold posting-work gap against effective support $4{,}000$; the previous $56$-fold example violated probability constraints.
• ColBERT preserves token vectors and scores a sum of row maxima after independent encoding. A fixed per-token ANN depth can still omit the globally best MaxSim document.
• The reported ablations show different losses under one recipe, not universal architecture gaps. Match precision, vector width and score units when pricing them.
• ColBERTv2 uses centroid identifiers and quantized residuals. PLAID uses centroid proxies before reconstructing survivors; compression and pruning need quality checks, and selected-list sizes are not bounded by their global average.
• RRF combines ranks without raw-score calibration. Its constant and list depth determine agreement trade-offs; extra correlated lists are not independent evidence and can change the fused head.

The story

Imagine one large library with a librarian named Mira. The old card catalog uses BM25, a literal-word clerk that files a book only under words printed in it. A patron asks for “laptop won’t charge,” while the manual says “AC adapter fails to supply power.” Mira owns the right manual, but the catalog cannot connect the two phrasings. Mira upgrades each catalog card with SPLADE. SPLADE is a learned sparse clerk that predicts useful vocabulary labels, including labels absent from the page. The manual can now receive a positive “charge” label even if that word never appears. Mira still uses the same inverted catalog. She has changed the weights written on the cards, not the shelves or the lookup rule. The learned vocabulary produces many possible labels. ReLU gives exact blanks that need no posting, while the logarithm reduces each large logit's marginal influence without imposing a hard cap. Repeating the same positive contribution still scales a sum-pooled weight linearly. FLOPS regularization penalizes crowded mean-weight dimensions; its relationship to posting traffic also depends on which dimensions become nonzero. Some questions need more than vocabulary labels. Mira then uses ColBERT, a reference method that keeps a small note for every query token and every document token. Each query note scans the document notes and keeps its best match. MaxSim is this best-match rule. The interaction happens late, after Mira has prepared every document note offline, so she preserves detail without rereading every document through a joint model. Mira compares three controlled changes under one training recipe: collapsing token vectors, replacing maxima with means, and removing augmented query positions. In the reported experiment, token collapse has the largest loss, then mean pooling, then removal of query augmentation. Those separate ablations do not assign independent additive shares of quality or prove that every well-trained single-vector model must lose the same amount. Token vectors occupy more space. ColBERTv2 stores a centroid identifier plus a quantized residual for each one. This preserves a selected cluster label exactly, not every semantic distinction in the original vector. PLAID reuses centroid scores to rank and prune candidates, then reconstructs the final survivors. Both quantization and candidate pruning can change rankings, so Mira checks quality at every stage. Mira keeps the literal and learned catalogs because each may help different requests. Their raw scores have different scales, so a direct uncalibrated sum needs validation rather than a claim of impossibility. RRF gives reciprocal-rank contributions and can reward agreement. Its rank constant, list depths, weights and treatment of missing documents determine the result; two correlated catalogs do not become independent corroboration. The full lesson stays inside this library. Learn better catalog labels, balance crowded drawers, retain token notes when detail pays, compress shared patterns, postpone expensive reconstruction, and fuse distinct catalogs only with a rule whose exchange rate you can explain.

Decoder table

Core mechanics

Mathematical conventions

Use decimal $\mathrm{kB},\mathrm{MB},\mathrm{GB},\mathrm{TB}$ for powers of ten and binary $\mathrm{KiB},\mathrm{MiB},\mathrm{GiB}$ for powers of two: $1\,\mathrm{GB}=10^9\,\mathrm B$ and $1\,\mathrm{GiB}=2^{30}\,\mathrm B$. fp32 and fp16 use $4\,\mathrm B$ and $2\,\mathrm B$ per value. One multiply-accumulate (MAC) counts as two FLOPs in the work proxies. Vector or posting payloads exclude dictionaries, source text, graph links, identifiers not already counted, allocation, replicas and runtime buffers unless stated. Keep full precision until reporting; $\approx$ marks rounding or modeling approximation. For sparse examples, let $\mathcal V$ be the vocabulary with size $V=\lvert\mathcal V\rvert=30{,}522$, $N=8{,}841{,}823$, $p_j=\Pr(w_j^d\gt 0)$ and $q_j=\Pr(w_j^q\gt 0)$ describe document and query activation profiles. Thus $0\le p_j,q_j\le1$ and $\bar u_d=\sum_jp_j$ is average nonzero count. Learned mean weight $\mu_j=\mathbb E[w_j^d]$ is not generally $p_j$. The exhaustive posting-work proxy $N\sum_jq_jp_j$ is distinct from actual latency with pruning, query encoding, score accumulation and top-result selection. For the late-interaction payload examples, use the separately stipulated rounded corpus $N_c=8.8\times10^6$, $n_d=68$ indexed token vectors per passage, $N_q=32$ query positions and projection width $h_c=128$. Do not silently mix this with the exact sparse corpus count. A BERT-base encoder has $P=110\times10^6$ parameters; $2PT$ forward FLOPs for $T$ processed positions is approximate and omits attention-length effects, projections and other work. Lengths omit any additional special tokens unless included in the stipulated count. Dividing work by hardware rates is not a measured latency, physical lower bound or request-percentile guarantee. MRR is a fraction: $\mathop{\mathrm{MRR}}\nolimits @10=Q^{-1}\sum_{i=1}^{Q}\mathbf1[r_i\le10]/r_i$, with zero contribution if no relevant result is found, where $r_i$ is the first relevant one-based rank. One scaled MRR point is $0.01$ on this scale; relative loss instead divides an absolute score change by a specified baseline. Passage recall, answer-hit accuracy and ANN neighbor recall have different reference sets and denominators. The cited scores, ablations and latency profiles are reported inputs; they are not all one matched experiment. In fusion, use $\kappa\ge0$ for the RRF rank constant, $m$ for list depth and $L$ for list count, distinct from BM25 $k_1$, projection width and rerank depth. A document absent from a truncated list contributes zero; ranks are one-based, with a declared deterministic tie policy. Min-max normalization requires a nonzero score range and a documented constant-list fallback. Normalized or fused scores are not automatically probabilities. Historical software, benchmark and hardware assertions remain reported source claims, not independent verification.

21.1 SPLADE: MLM-predicted term importance and implicit expansion

The shared sparse scoring form

• What: Let $V$ be a shared abstract term-coordinate set with $V=30{,}522$ in the SPLADE WordPiece example. Weights $w_j^q,w_j^d$ refer to query and document coordinate $j$.
• Why: Sparse dot-product scoring supports inverted lists, with contributions only from nonzero query dimensions and stored nonzero document dimensions.
• Scope: Real BM25 analyzers need not use WordPiece; sharing the scoring shape does not make every implementation's vocabulary or posting format identical.
• Cost: Exhaustively visiting eligible postings is one work model. Dynamic pruning, quantization and top-result selection change execution cost.

For one unfielded BM25 variant, let $f_{j,d}$ be analyzed term count, $L_d$ document length, $\overline L\gt 0$ average length, $k_1\gt 0$ and $0\le b_{\mathrm{BM25}}\le1$. Use the guarded positive IDF convention from Chapters 18 and 20, and ignore query-frequency weighting in this particular decomposition:

• What: A zero document term count contributes zero under this lexical variant; learned expansion changes that literal-support property.
• Why: An exact posting match is evidence of analyzed term occurrence, not proof of relevance. BM25 can use other query terms and length effects, but does not itself contextualize the word “bank.”
• Failure case: A relevant passage may paraphrase all informative query terms and have no analyzed overlap. Translation, expansion or another retrieval route changes that premise.
• Reported scenario: The opening example gives BM25 request $p_{99}=40\,\mathrm{ms}$ and an audited unacceptable-candidate rate $12\%$. These are scenario observations, not consequences of the formula or a general BM25 failure rate.

Discrete expansion versus direct vocabulary weighting

• Discrete expansion: The cited docT5query configuration generates forty possible queries, appends their text and indexes it with BM25. Generation settings change the resulting corpus and term counts. Ordinary backpropagation does not pass directly through discrete decoding, although other training estimators or surrogates are possible.
• Reported result: The chapter gives $\mathop{\mathrm{MRR}}\nolimits @10=0.277$ versus BM25 $0.184$ in that comparison; do not combine these automatically with the separate ColBERT baseline.
• Direct weights: SPLADE's MLM vocabulary head scores vocabulary pieces at contextual positions, so absent pieces can receive weight without generating a string. This is one expansion parameterization, not a theorem that no other architecture can expand absent terms.
• Intermediate size: At $n=128$ and $V=30{,}522$, there are $nV=3{,}906{,}816$ logits, or $15.627264\,\mathrm{MB}$ if materialized in fp32. Implementation and streaming can change peak memory.

Here $T$ is the MLM dense/GELU/LayerNorm transform, $E_j$ the tied vocabulary embedding and $b_j$ its output bias. The position set used for pooling must follow the attention and special-token policy; padding positions must not accidentally create indexed terms.

Exact zeros, saturation, and pooling

• What: ReLU sets nonpositive logits to zero. For positive logits, $\ln(1+\ell)$ grows sublinearly but remains unbounded; its derivative is $1/(1+\ell)$.
• Why: Exact output zeros can be omitted from the inverted index. The log transform reduces marginal scale, not the total number of active dimensions.
• Limit: ReLU can leave many positives, and sum pooling still adds repeated contributions. It does not impose a posting budget or a hard per-term cap.
• Cost: Sparse serving does not imply sparse indexing computation: the vocabulary head can still be dense.

Five logits equal to twelve have raw sum $60$, versus $5$ for five logits equal to one, a raw ratio $12$. Transformed sums are $5\ln13\approx12.824746787$ and $5\ln2\approx3.465735903$, ratio $\ln13/\ln2\approx3.700439718$. The transform compresses the ratio; doubling the number of identical positions still doubles either sum-pooled weight. Pooling removes explicit position indexing only after contextual encoding, so the output is a vocabulary-weight vector rather than a literal order-free input model. A max-pooled variant uses $w_j^d=\max_i a_{ij}$. The chapter reports $\mathop{\mathrm{MRR}}\nolimits @10$ changing from $0.322$ to $0.340$ for a cited variant, but not reproducing universally. Treat the result as a reported configuration comparison, not proof that max pooling always wins or that pooling alone explains every v2 gain.

Training and interpretability

• Training: The cited SPLADE v1 recipe uses in-batch candidates and one BM25-mined hard negative per query. Mask known positives and duplicates; mined candidates are not exhaustively judged negatives.
• Objective: Ranking supervision can train the vocabulary weights end to end, with ReLU's local zero derivatives and shared parameters accounted for. It does not automatically enforce sparsity or calibrated expansion.
• Reported results: The chapter gives $\mathop{\mathrm{MRR}}\nolimits @10=0.322$ for v1 and $0.368$ for a distilled v2 configuration, versus $0.184$ BM25 and $0.277$ docT5query in that comparison. Distillation, training and architecture changes must not all be attributed to one pooling operation. SPLADE coordinates are inspectable vocabulary pieces, not necessarily whole readable words or a faithful explanation of the complete ranking decision. The source suggests reviewing the top twenty coordinates on a few hundred documents. Check context, negation, brands and unsupported expansions against judgments; deleting a coordinate can remove useful matches too. An expanded posting does not certify that its label literally occurred in the source.

Worked index economics

For a payload example use $N=8{,}841{,}823$, $V=30{,}522$ and $8\,\mathrm B$ per posting: a four-byte document identifier plus four-byte weight. Assume forty stored BM25 terms per passage. To make the query arithmetic explicit, the following table uses uniform activation across the vocabulary, not an observed natural-language frequency distribution. For the unregularized row, $p_j=0.30$ gives average $0.30V=9{,}156.6$ active dimensions; its fractional totals are expected quantities, not literal fractional records.

At $160$ stored pairs, each document uses $1{,}280\,\mathrm B$ under this posting format. A width-$768$ fp32 vector uses $3{,}072\,\mathrm B$; corpus payloads are $11.31753344$ versus $27.162080256\,\mathrm{GB}$, a ratio $2.4$. This is not an all-in sparse/dense index ratio; real engines use different compression, dictionaries and auxiliary structures. The vocabulary projection alone has proxy $2(128)(768)(30{,}522)=6{,}000{,}869{,}376$ FLOPs per passage, compared with encoder proxy $2(110\times10^6)(128)=28{,}160{,}000{,}000$ FLOPs, a ratio $21.309905\%$. The preceding dense transform adds another $2(128)(768)^2=150{,}994{,}944$ FLOPs before nonlinearities, normalization, bias and pooling. The head percentage alone does not establish indexing throughput or the dominant production bill. At five hundred million chunks, payloads are $1.536\,\mathrm{TB}$ for width-$768$ fp32 dense vectors, $160\,\mathrm{GB}$ for forty eight-byte postings and $640\,\mathrm{GB}$ for one hundred sixty postings. Learned sparse expansion still uses lexical coordinates, but does not provide a hard literal-containment guarantee. Compare measured request $p_{99}$, candidate coverage and final quality before choosing one learned index over a lexical/dense pair. An average of one hundred sixty nonzeros—four times the forty-term baseline—is a source starting heuristic, not a universal optimum. Query sparsity can reduce posting traffic without reducing the dense query encoder/head work. Use an index that supports learned posting weights and its quantization/pruning contract. Dense materialization of all $30{,}522$ fp32 coordinates costs $122{,}088\,\mathrm B=122.088\,\mathrm{kB}$ per document and $1.079480486424\,\mathrm{TB}$ over this exact corpus. The cited SPLADE-doc option removes the learned query-side encoder/expansion in favor of lexical query coordinates; evaluate its quality. docT5query is another option when the serving engine accepts expanded text but not custom impact weights.

21.2 FLOPS regularization: making sparsity a trainable objective

Model the work the index performs

• What: Let $p_j$ be corpus activation probability and $q_j$ query activation probability. An exhaustive traversal opens list $j$ with probability $q_j$ and its modeled length is $Np_j$.
• Why: Expected posting visits depend on the product of the two profiles, not just their separate nonzero totals. One posting contribution uses one MAC in this proxy.
• Scope: Corpus frequencies can be fixed empirical fractions; query randomness supplies the expectation. Dynamic skipping, caches, score quantization and query encoding are not counted.

The exact $\ell_0$ support count is piecewise constant and has zero derivative almost everywhere, so naive gradient descent on it is unsuitable. The identity $\mathbb E\lVert w^d\rVert_0=\sum_jp_j=\bar u_d$ is about nonzero indicators, not an identity for $\ell_1$ weight mass. With arbitrary nonnegative weights, shrinking every positive weight reduces $\ell_1$ without changing any support. Calling $\ell_1$ the tightest convex relaxation needs a domain: on a bounded unit $\ell_\infty$ box it is the convex envelope of $\ell_0$, not an unqualified statement on unbounded weights. Support budgets still require measurements, thresholds or further assumptions. For the following tractable toy only, assume proportional activation profiles $q_j=(\bar u_q/\bar u_d)p_j$, with $\bar u_d\gt 0$ and probabilities remaining in $[0,1]$. The worked case has $\bar u_q=30\lt 160=\bar u_d$, so the query constraint is feasible. This assumption is not implied by the FLOPS penalty:

Then expected cost and effective support become:

Cauchy–Schwarz gives $m_{\mathrm{eff}}(p)\le V$, with equality for equal nonzero popularity across all vocabulary coordinates. Also $\sum_jp_j^2\le\sum_jp_j=\bar u_d$ because $p_j\le1$, so $m_{\mathrm{eff}}(p)\ge\max(1,\bar u_d)$. At $\bar u_d=160$, the tight minimum is $160$, achieved by one hundred sixty always-active dimensions. Thus the maximum cost ratio between feasible profiles at these fixed proportional counts is $30{,}522/160=190.7625$, not the vocabulary size. Against the specific $m_{\mathrm{eff}}=4{,}000$ comparison below, the greatest possible ratio is $25$.

Why a Zipfian profile is expensive

An uncapped reciprocal profile has harmonic sums $H_V=\sum_{j=1}^{V}1/j\approx10.903435060$ and $H_V^{(2)}=\sum_{j=1}^{V}1/j^2\approx1.644901304$. Its scale-invariant effective support is $H_V^2/H_V^{(2)}\approx72.274790$. This is a valid concentration statistic for arbitrary nonnegative weights, but not a feasible probability profile at mean support one hundred sixty: normalization would require $p_1=160/H_V\approx14.674275\gt 1$. The previous fifty-six-fold posting-cost example therefore mixed weight mass with activation probabilities. A feasible concentrated example is $p_j=\min(1,c/j)$, choosing $c$ so $\sum_jp_j=160$. Numerically $c\approx19.168819842$; the first nineteen probabilities equal one. Then $\sum_jp_j^2\approx37.827100078$ and $m_{\mathrm{eff}}(p)\approx676.763483$. This is a constructed capped-Zipf example, not a theorem that an $\ell_1$-trained model must learn this profile. Harmonic approximations include finite-size terms; do not replace $H_V$ by $\ln V+\gamma$ as an exact equality.

FLOPS as load balancing

For a batch of $B$ nonnegative document-weight vectors, define a mean weight and the named FLOPS surrogate. These are real weights, not automatically binary activation probabilities:

For this penalty, $\partial\mathcal R_{\mathrm{FLOPS}}/\partial w_j^{(b)}=2\bar a_j/B$. For $\mathcal R_1=B^{-1}\sum_{b,j}w_j^{(b)}$, the derivative on a positive weight is $1/B$. Mean weights $2.0$ and $0.05$ therefore have a fortyfold FLOPS derivative ratio before coefficients and the activation chain rule. The pressure is on output weights; derivatives through ReLU/log pooling and shared encoder parameters are different quantities. For $B\gt 1$, squaring the mean introduces cross-document coupling. Under IID batches, $\mathbb E[\bar a_j^2]=\mu_j^2+\mathop{\mathrm{Var}}\nolimits(w_j)/B$, not exactly $\mu_j^2$. Batch size one lacks cross-document coupling. Finite-batch variance, active-weight magnitudes and the query/document relation all affect how this surrogate translates into support and real posting traffic. For a nonzero mean-weight vector $\mu$, define $m_{\mathrm{eff}}(\mu)=(\sum_j\mu_j)^2/\sum_j\mu_j^2$. At fixed mean $\ell_1$ mass $M_1=\sum_j\mu_j$, the population mean-square term is $M_1^2/m_{\mathrm{eff}}(\mu)$, so minimizing it spreads that weight mass. Equating this with $\bar u_d^2/m_{\mathrm{eff}}(p)$ additionally needs binary weights or a fixed common active amplitude. Arbitrary SPLADE weights need not satisfy it. FLOPS can encourage sparsity and load balance but does not guarantee a fixed support count, profile proportionality or latency optimum.

Separate query and document penalties

Document support affects persistent postings and traffic; query support affects posting traffic and transient query work. Both sides can affect relevance, encoder cost and caches. The source suggests trying $\lambda_q$ roughly an order of magnitude above $\lambda_d$ when query latency binds, but the coefficients depend on loss normalization, weight scales, parameter sharing and task. Stronger query regularization does not automatically leave the document profile unchanged in a shared encoder; measure both after training. The all-zero output minimizes either nonnegative penalty. A strictly negative logit has zero local derivative through ReLU, but this alone does not make a vocabulary dimension permanently dead: shared parameters can move from other examples, and optimizer state or weight decay can change logits. A completely inactive model can be locally stuck if every training gradient reaches only these zero-derivative paths and no other update acts. The source describes a quadratic regularization warm-up; trying the first ten to fifteen percent of steps is a scheduling heuristic, not a guarantee against collapse or proof that full initial regularization always kills outputs.

Worked cost profiles

Use the exact sparse corpus $N=8{,}841{,}823$, average document support $\bar u_d=160$ and query support $\bar u_q=30$. Keep proportional probability profiles explicit; this is a different query support from the preceding one-hundred-coordinate payload example.

The feasible concentrated and balanced examples have the same average document support and a posting-work ratio $4{,}000/676.763483\approx5.910484$, not fifty-six. Reducing query support from thirty to eight gives another factor $30/8=3.75$ only with the document profile and proportionality held fixed. The balanced document profile is feasible: take $p_j=0.04$ on four thousand dimensions and zero elsewhere; its corresponding query probabilities are $0.0075$. The balanced and capped-Zipf proxies are approximately $114.4575$ and $676.499267$ times the earlier uniform BM25 posting estimate $92{,}699.802110$ MACs. These compare different constructed query/document profiles, not shipped query latency. The invalid uncapped calculation does not justify a six-thousand-four-hundred-fold production claim. WAND and BlockMax-WAND can skip contributions using upper bounds; their benefit depends on score distributions, impact quantization, list order, cutoffs and implementation. The source reports difficulties with dynamic pruning for some learned sparse distributions, not a theorem that every SPLADE index prunes worse than BM25. Evaluate document-at-a-time, impact-ordered and score-at-a-time engines on the deployment workload. Report document/query support distributions, activation-based effective support, mean-weight concentration and measured request tails together. Estimating frequencies from one hundred thousand vectors is a source sampling heuristic; unseen rare dimensions and domain shift add uncertainty. A target of one hundred sixty document nonzeros and effective support at least four thousand is a candidate budget, not a theorem. At five hundred million chunks that posting payload is $640\,\mathrm{GB}$ under this format. Compare training-time regularization with serving-time top-coordinate truncation: neither universally preserves recall or fixes skew. Recompute profiles after changing corpus, tokenizer, thresholds, weights or domain.

21.3 ColBERT and late interaction

Locate the architectural gap

• Architecture: A single-vector bi-encoder scores two query-independent-side vectors. A standard cross-encoder jointly conditions token states on the current query/document pair; reusable final document states are therefore unavailable in that baseline, even though raw text and some preprocessing can be cached.
• Representation limit: A simple mean gives equal coefficients to contextual token vectors, not necessarily equal semantic importance to the original words. Contextual states can already encode salience. A single vector is a bottleneck, but its width alone does not prove a fixed quality gap.
• Reported comparison: The chapter gives cross-encoder $\mathop{\mathrm{MRR}}\nolimits @10=0.347$ and $10{,}700\,\mathrm{ms}$ at candidate depth one thousand. Keep measured configuration and approximate work models distinct.

Keep token vectors and interact late

• What: ColBERT independently encodes the two texts, projects token states to $h_c=128$ and normalizes nonzero token vectors. A zero vector or empty document requires an explicit masking/fallback policy rather than division by zero or a maximum of an empty set.
• Query positions: The cited recipe augments queries to $N_q=32$ positions with mask tokens. These contextual outputs are not zero-padding vectors.
• Why: Documents remain precomputable, while query-token-specific matching is delayed until scoring. Contextual encoding still precedes the late interaction.
• Cost: Payload scales with indexed document-token count and vector width/precision, not merely passage count.

For a single query row, suppose a document of $68$ vectors has one similarity $0.95$ and the other $67$ similarities $0.10$. Replacing its maximum by its mean yields:

A comparison row with all similarities $0.10$ scores $0.10$. Maximum similarity has ratio $0.95/0.10=9.5$ and additive gap $0.85$, while the mean has ratio $1.125$ and gap $0.0125$. These are similarity-score comparisons, not likelihood ratios or calibrated evidence. With one strong cell and a fixed background, the mean gap shrinks as $0.85/n_d$. MaxSim can also match several query tokens to the same document token and does not itself enforce joint factual consistency.

End-to-end candidate generation

A token-driven candidate stage can issue ANN probes for query vectors, map hits to passages, deduplicate and rescore their union with MaxSim. This changes the first-stage candidate set; it does not remove all coverage ceilings. A fixed probe depth is not guaranteed to retrieve the global MaxSim winner. For example, take orthogonal unit query vectors $e_1,e_2$, two single-token distractors $e_1,e_2$, and a single-token relevant document $(e_1+e_2)/\sqrt2$. That document has total score $\sqrt2\gt 1$, but each query token's nearest single token is its corresponding distractor. Two top-one probes omit the highest-scoring document. The source reports end-to-end $\mathop{\mathrm{Recall}}\nolimits @1000=96.8\%$ versus BM25-candidate reranking $81.4\%$. If a reranker receives and returns exactly the same thousand documents, its recall at that same depth is unchanged by reordering. At smaller output depths ranking can help. Token ANN, filters and later pruning impose their own candidate-survival limits, and passage recall is not numerically a universal NDCG ceiling.

Worked architecture costs

For matched work proxies use $N_c=8.8\times10^6$, $n_d=68$, $N_q=32$, $h_c=128$, fp16 token vectors, $P=110\times10^6$ and a fixed candidate depth $K_r=1{,}000$. The cross-encoder proxy processes $32+68=100$ positions per pair, with any extra special positions omitted. Token candidate generation, projection/normalization, maximum reductions, data movement and selection are not included in the dot-product FLOP formulas.

The query encoder proxy is $2(110\times10^6)(32)=7.04\times10^9$ FLOPs. Candidate token dot products add $2(1{,}000)(32)(68)(128)=557{,}056{,}000$ FLOPs, for total $7.597056\times10^9$. These shares are approximately $92.667475\%$ encoding and $7.332525\%$ token dots, summing to one hundred percent. Max comparisons, row summation, projections and system work remain outside this accounting. At the matched lengths, the cross/ColBERT work-proxy ratio is approximately $2.2\times10^{13}/(7.597056\times10^9)=2{,}895.858606$. The previous ninety-seven-trillion-FLOP figure is not implied by those lengths; under the same $2P$ rule it would require roughly $440.909091$ processed positions per pair. Do not combine it with a rounded seven-billion denominator as though all numbers describe one experiment. The reported latency ratio is $10{,}700/61\approx175.409836$. Dividing an unmatched FLOP ratio by that measured ratio does not prove a seventy-ninefold overstatement or isolate overhead. The cited profile allocates $13$ of $61\,\mathrm{ms}$ to encoding/interaction and the remaining $48\,\mathrm{ms}$ to gathering, stacking and transfers. That profile motivates a data-movement optimization in its configuration, not a universal bottleneck for all late-interaction systems. Token payload is $68(128)(2)=17{,}408\,\mathrm B$ per passage. The width-$768$ fp32 single-vector example is $3{,}072\,\mathrm B$, giving ratio $17/3\approx5.666667$. At the rounded corpus $N_c$, totals are $153{,}190{,}400{,}000\,\mathrm B\approx142.669678\,\mathrm{GiB}$ and $27{,}033{,}600{,}000\,\mathrm B\approx25.177002\,\mathrm{GiB}$. The comparison deliberately uses different widths/precisions and excludes auxiliary index structures; it is not a universal multi-vector multiplier. At fixed passage count and storage format, doubling indexed token count doubles raw multi-vector payload. A single-vector payload stays constant only if chunk count and width remain fixed; longer chunks can change tokenization limits, quality and serving work. For $N_c$ and sixty-eight vectors per passage, width-$128$ fp32 payload is $285.339355\,\mathrm{GiB}$ and width-$24$ fp16 payload is $26.750565\,\mathrm{GiB}$, ratio $10.666667$. The source's rounded reported footprints are $286$ and $27\,\mathrm{GiB}$, a ratio approximately $10.592593$; do not equate rounded empirical totals with the exact toy count. This change includes both width and precision. Holding fp16 fixed, width $128\to24$ gives ratio $5.333333$ instead. The cited quality operating points are $\mathop{\mathrm{MRR}}\nolimits @10=0.349$ and $0.339$, an absolute loss $0.010$, or one scaled MRR point. Relative loss from the larger baseline is $0.010/0.349\approx2.865330\%$; relative gain of the larger over the smaller is $0.010/0.339\approx2.949853\%$. These are different denominators and are not a universal marginal price of dimensions. The source reports end-to-end retrieval at $458\,\mathrm{ms}$ versus reranking at $61\,\mathrm{ms}$, ratio approximately $7.508197$ for those configurations. End-to-end retrieval replaces the BM25 candidate ceiling with token-search and pruning constraints; it does not eliminate candidate loss. A sub-hundred-millisecond target may motivate shallow reranking, but nominal or average measurements do not establish a request-tail SLO. The source's roughly one-million-chunk affordability boundary is a workload heuristic; evaluate payload, all-in index size, candidate coverage and measured latency.

21.4 The three ablations that show what makes ColBERT work

Read controlled deletions correctly

The chapter reports all three variants reranking BM25's top thousand passages on MS MARCO development data, with full $\mathop{\mathrm{MRR}}\nolimits @10=0.349$. The following differences use that baseline and a fractional MRR scale. They are separate reported ablations, not additive causal allocations or a complete factorial experiment.

Against the separately reported BM25 $0.187$ baseline in this comparison, the full model gains $0.349-0.187=0.162$ and the pooled variant $0.285-0.187=0.098$. Token collapse loses $0.064/0.162\approx39.506173\%$ of that measured improvement. This is a descriptive gain ratio, not a fraction of all useful knowledge or a universal attribution of architectural value. The absolute-drop ratio is $0.064/0.018\approx3.555556$; using the rounded relative percentages gives a less precise comparison. In this recipe the token-collapse ablation loses more than the mean-score ablation. A fixed representation cannot recover a distinction if it maps the relevant inputs identically, but this does not prove which distinctions another trained representation can preserve, or that granularity and aggregation have independent effects. A literal grid-based mean implementation still computes the same dot-product grid, but the chapter's unweighted row-mean score has an exact real-arithmetic factorization:

For this score alone, precompute the document mean and score one vector pair; retaining the full token grid is unnecessary. Do not renormalize pooled vectors and claim the same score, because document-dependent norm changes can change ranks. Finite-precision pooling introduces its own numerical differences. If a separate token-ANN candidate stage is retained, it may still need token vectors; scorer and candidate-index storage must be distinguished. Thus “mean saves zero storage and zero FLOPs” is not a mathematical consequence of the stated score. MaxSim's nonlinearity prevents this simple factorization and preserves per-query-token best matches. Mask-augmentation positions pass through the contextual encoder and can learn useful latent query features; they are not guaranteed literal synonyms predicted by pre-training alone. One independently supplied, compatible query vector adds $n_dh_c$ dot-product MACs per candidate, plus maximum/accumulation work. Re-encoding an augmented text can also change every original query vector, unlike merely appending a fixed vector after encoding. End-to-end token retrieval may require new ANN probes and a changed candidate union. Document-side expansion likewise changes stored vectors/postings and indexing work. Evaluate arbitrary term-table or centroid-vector additions for training compatibility rather than assume equivalence to the cited mask ablation.

Price each deletion

For consistent payload arithmetic, use the fp16 width-$128$ baseline $142.669678\,\mathrm{GiB}$ and reranking proxy $7.597056\times10^9$ FLOPs. The following storage-per-score comparisons are illustrative ratios of operating-point differences, not causal derivatives or confidence intervals.

• Token-collapse payload: One width-$128$ fp16 vector is $256\,\mathrm B$ per passage, or $2.098083\,\mathrm{GiB}$ at $N_c$. Against the raw token payload it saves $140.571594\,\mathrm{GiB}$. Dividing by the reported $6.4$ scaled MRR-point loss gives $21.964312\,\mathrm{GiB}$ per point in this illustrative comparison.
• Width payload: Holding fp16 fixed, width $128\to24$ saves $115.919113\,\mathrm{GiB}$. Pairing this payload difference with the reported one-point operating-point loss gives a descriptive ratio $5.277612$ times the preceding storage-per-point number. The source's footprint/quality configurations are not proof that width alone caused this result.
• Mean-score lever: The pure mean-dot score can store an aggregate document vector instead of all token vectors; it has potential scorer-storage and interaction savings. A retained token candidate index changes the all-in saving. Its reported $0.018$ MRR loss is not payment for mathematically zero efficiency gain.
• Augmentation proxy: If processed query positions drop from thirty-two to eight, including the chosen special-token policy, the encoder proxy becomes $1.76\times10^9$ FLOPs and token-dot work $139{,}264{,}000$, total $1.899264\times10^9$, exactly one quarter of this matched proxy. Eight query words plus extra positions are a different length. For an Amdahl-style scenario, hold the reported $48\,\mathrm{ms}$ gathering/transfer component fixed and suppose the affected $13\,\mathrm{ms}$ component becomes four times faster. Then time would be $48+13/4=51.25\,\mathrm{ms}$, saving $9.75\,\mathrm{ms}$ or $15.983607\%$ of the baseline. This is conditional arithmetic, not a measured new latency or a universal upper bound derived from FLOPs. The reported augmentation score drop is $1.719198\%$ relative MRR, a different metric. Fixed shapes can aid batching, but modern ragged kernels and changed candidate counts require benchmarking. For a precomputed appended query vector, the extra dot work is $2(68)(128)=17{,}408$ FLOPs per candidate and $17{,}408{,}000$ over a thousand candidates. That is approximately $0.229141\%$ of $7.597056\times10^9$. It excludes producing/normalizing that vector, row maxima, extra token probes, candidate changes and data movement; it is not the percentage of end-to-end latency. These ablations do not prove all single-vector retrieval is $18.338109\%$ worse. The source reports ANCE $\mathop{\mathrm{MRR}}\nolimits @10=0.330$ with a different training/negative recipe. A one-vector footprint is one sixty-eighth of the token payload only at the same width-$128$ fp16 format; the width-$768$ fp32 payload is smaller by a factor $5.666667$. Do not assign the former ratio to ANCE without specifying its dimensions and precision. A width-$24$ fp16 token payload is $26.750565\,\mathrm{GiB}$, but fitting a $30\,\mathrm{GiB}$ device/index budget still depends on auxiliary structures and runtime memory. Measure the relevant candidate and final-quality differences rather than apply a universal one-to-two-recall-point cutoff or assume short texts erase every architecture gap.

21.5 Making multi-vector affordable: ColBERTv2 and PLAID

Factor shared identity from contextual detail

The rounded corpus $N_c=8.8\times10^6$ with sixty-eight stored vectors per passage has $T_c=N_cn_d=598{,}400{,}000$ token vectors. A width-$128$ fp16 vector is $256\,\mathrm B$. Actual filtered/tokenized lengths vary; all following totals condition on this average and format.

• What: Learn a centroid codebook, assign each token vector to a centroid and quantize its residual. The stored centroid identifier is a cluster address, not an exact lexical-token identity.
• Why: If within-cluster residuals have a smaller useful range than raw coordinates, low-bit residual coding can reduce distortion at a given size. This is a distributional advantage to measure, not a guarantee for every domain.
• Limit: Direct coordinate quantization can lose important detail, but it is not mathematically required to fail; error depends on scaling, codebook and retrieval margins. Residual quantization is also lossy.
• Cost: Two bits give four code levels per dimension, with packing and metadata assumptions stated below.

With $K_c=2^{18}=262{,}144$ centroids, a packed identifier needs at least eighteen bits; this example stores it in $4\,\mathrm B$. A two-bit width-$128$ residual uses $128(2)/8=32\,\mathrm B$, so a record is $36\,\mathrm B$ rather than $256\,\mathrm B$, a payload-only factor $256/36\approx7.111111$. Assuming fp16 centroids, the shared codebook is $(262{,}144)(128)(2)=67{,}108{,}864\,\mathrm B=64\,\mathrm{MiB}$, approximately $0.311520\%$ of compressed token payload. Scale tables, offsets and other metadata are not included. The source relates this design to centroid/residual quantization and reports little or no measured quality loss in a comparison. Quality neutrality is not guaranteed by the representation identity. Residual drift, clipping, codebook mismatch and reconstruction/normalization policies can change ranks. For unit query rows and document-vector perturbations $e_j=\widehat v_j-v_j$ measured after the scoring pipeline's normalization policy, a useful bound is

If both documents have error at most $\varepsilon$ per vector, an original score gap greater than $2N_q\varepsilon$ is sufficient to preserve their order. Smaller gaps need not flip, but are not protected by this bound. This is a deterministic error statement under its norm assumptions, not a benchmark guarantee.

Reuse centroids in the PLAID funnel

1. Score the $N_q$ query vectors against the shared centroid table, then probe selected centroid lists and map hits to candidate passages. Candidate generation still reads the required posting metadata; “no residuals” does not mean “no other reads.”
2. Apply the configured centroid-pruning rule. Similarity thresholds and probe limits are approximate candidate controls, not automatic exact MaxSim bounds.
3. Use centroid identifiers for a cheaper proxy score, such as $\widetilde S(q,d)=\sum_i\max_j E_{qi}^{\mathsf T}C_{t(v_j)}$, and retain configured candidate depths. The proxy omits residual contributions and can reorder documents.
4. Reconstruct surviving quantized vectors and compute the full retained-vector score. “Exact” here means scoring that reconstructed representation, not recovering pre-quantization vectors or the exhaustive global ranking. Generic IVF-PQ is not inherently opaque until full reconstruction: asymmetric distance computation can score product-quantization codes with lookup tables, and generic indexes can use coarse centroids and pruning. The source reports PLAID gains from a retrieval-specific centroid-interaction/decompression funnel and optimized kernels. It does not prove that every alternative must decompress all candidates, or that sharing a codebook alone explains a measured speedup.

Worked storage and traffic

Use $K_c=2^{18}$ centroids, two residual bits per dimension, $N_q=32$, $n_d=68$ and two probes per query position. The example funnel retains $n_{\mathrm{docs}}=256$ then $n_{\mathrm{docs}}/4=64$ passages. For traffic arithmetic, separately stipulate $U=146{,}112$ unique candidate passages; that count is not an upper bound derivable from average centroid-list length. All traffic rows below count compressed input payload, not complete memory traffic.

The compressed payload plus codebook is $20.125423\,\mathrm{GiB}$, saving $122.544254\,\mathrm{GiB}$ against this raw fp16 payload. The size ratio including that codebook is approximately $7.089027$, rather than exactly the per-record factor. The separate width-$24$ fp16 payload saves $115.919113\,\mathrm{GiB}$ and is paired with a reported one-point MRR operating-point difference; neither comparison proves lossless quality or a causal width/compression trade-off. Across all token-assignment lists, the mean length is $598{,}400{,}000/262{,}144=2{,}282.71484375$ token entries. Sixty-four uniformly selected distinct lists would have expected total $146{,}093.75$ token hits. Query-selected lists are not uniform, popular lists can be much longer, probes can repeat centroids, and many token hits can map to one passage. An index with per-centroid deduplicated passage postings has another list-size distribution. Thus neither $146{,}112$ unique passages nor a $1.7\%$ corpus upper bound follows from that mean. The separately assumed $U$ is about $1.660364\%$ of $N_c$, purely for the worked payload comparison. Under that stipulated $U$, full compressed-record reads are $341.112305\,\mathrm{MiB}$ and identifier-only reads $37.901367\,\mathrm{MiB}$. Rereading complete records for sixty-four survivors adds $156{,}672\,\mathrm B=153\,\mathrm{KiB}$, for $38.050781\,\mathrm{MiB}$ total. The ratio is approximately $8.964660$, slightly below nine; $36/4=9$ holds only before the extra survivor read. Reusing already read identifiers would instead add only residual payload, giving $38.034180\,\mathrm{MiB}$ under this format. These are not all-in traffic totals. If both paths additionally read one cold $64\,\mathrm{MiB}$ codebook, the corresponding ratio becomes approximately $3.969713$. Centroid scores, posting metadata, code lookup, temporary buffers and reconstructed-vector writes matter too; merely writing the sixty-four fp16 reconstructed passages is $1{,}114{,}112\,\mathrm B$. Actual cache reuse and kernels determine reads and writes. Do not infer a ninefold latency improvement from the record-size ratio. The payload reduction lies within the source's reported six-to-tenfold ColBERTv2 size range. The source also reports up to sevenfold GPU and forty-fivefold CPU latency gains for PLAID in particular comparisons. A scoped record-traffic ratio does not establish or decompose those gains. Candidate pruning, cache behavior, batching, codebooks, CPU kernels and reshape/padding overhead all require profiling; their relative effects are not proved by the size arithmetic alone.

Quality, bit width, and codebook limits

Do not assign a training-quality gain to compression. The source reports $\mathop{\mathrm{MRR}}\nolimits @10$ changing from $0.360$ to $0.397$ with a denoised-distillation recipe using a twenty-two-million-parameter MiniLM teacher and a KL loss over sixty-four-way tuples. That is not a controlled proof that quantization improves relevance. One-bit residuals have two levels per coordinate rather than four, and use $4+16=20\,\mathrm B$ per token record. The payload is $11.146069\,\mathrm{GiB}$, or $11.208569\,\mathrm{GiB}$ with this codebook, saving $8.916855\,\mathrm{GiB}$ versus two-bit records. Halving the bit count does not imply halving numerical error or “precision”; distortion depends on quantizer and scale. Choose bit width from measured retrieval, including out-of-domain behavior. At $K_c=2^{18}$, centroid-dot work is $2(32)(262{,}144)(128)=2{,}147{,}483{,}648$ FLOPs, approximately $30.504029\%$ of the $7.04\times10^9$ query-encoder proxy. At $K_c=2^{20}$ it becomes $8{,}589{,}934{,}592$ FLOPs, approximately $122.016116\%$ of that proxy, before list traversal and scoring. Centroid count, list imbalance and token count create a work/coverage trade-off, not a fixed “few thousand per cell” rule. Instrument gold-passage survival against an exhaustive scoring reference on the same candidate set and also measure the initial candidate-stage loss; testing only survivors hides earlier omissions. Final MRR alone cannot identify the failed stage.

21.6 Hybrid retrieval and Reciprocal Rank Fusion

Why raw score fusion fails

Hybrid retrieval can help when dense and lexical paths have complementary errors, but neither “dense for meaning” nor “BM25 for codes” guarantees a slice win. The source's deployment vignette reports a four-point aggregate NDCG change alongside exact-string regressions; audit the relevant cohorts and candidate coverage. BM25 is not normalized to a global probability scale. For the positive-IDF variant and a fixed finite query, however, its score is bounded: $0\le s_{\mathrm{BM25}}(q,d)\le(k_1+1)\sum_{j\in q}\mathop{\mathrm{IDF}}\nolimits_+(j)$. Calling every fixed-query BM25 score unbounded ignores term-frequency saturation. Unit-vector cosine lies in $[-1,1]$, while an unnormalized dense dot product has a different range. An uncalibrated sum can be dominated by scale; it is not mathematically impossible to work, but needs explicit weighting and validation. For a list with score range $s_{\max}\gt s_{\min}$, min-max normalization is $\widehat s=(s-s_{\min})/(s_{\max}-s_{\min})$. It preserves ordering within that window and is invariant to positive affine score changes, but it is not probability calibration. Specify a constant-list fallback if the range is zero and how absent documents are handled; the worked example assigns missing-list contribution zero. A convex combination then uses $0\le\alpha\le1$:

The same raw score $18.2$ maps to $(18.2-6.1)/(31.4-6.1)\approx0.478260870$ in the first window and $(18.2-12.4)/(31.4-12.4)\approx0.305263158$ in the shorter window. That is a decrease $0.172997712$ in normalized-score units, or $36.172249\%$ relative to the first value. Window selection and outliers affect these values. Every nonconstant-list maximum becomes one, but other normalized gaps can still differ; it is not true that min-max erases all confidence-margin information. Raw rank summation assigns the same numerical rank difference to positions one/two and sixty-one/sixty-two. That is a design choice rather than a theorem that it must fail. Missing-list penalties and ties are additional choices; reciprocal ranks offer another rank-sensitive weighting.

RRF and the meaning of the rank constant

Here $L_\ell$ is a truncated ranked list, distinct from its list-count parameter $L$. A document must be in the candidate union to be scored, and tied input scores need a declared rank policy. Within one list, define $w(r)=1/(\kappa+r)$. Its ratio to a rank-one vote is:

This ratio reaches one half at $r=\kappa+2$ when that is an available integer rank. The rank constant controls the relative strength of a deep vote versus a top vote; it is not probability calibration or an assumption that different lists are independent. Compare a document at the same rank $r$ in all $L$ equally weighted lists with a different document at rank one in exactly one list and absent from the others. Only under that equal-rank/solo-hit comparison does the condition become:

For $L=2,\kappa=60$, common equal rank $r\le61$ strictly wins and $r=62$ ties the solo top hit. For $L=2,\kappa=0$, common rank one wins and common rank two ties. Unequal-rank agreement can also win: ranks one and one hundred contribute $1+1/100\gt 1$ at zero constant. For three-way equal-rank agreement with $\kappa=60$, ranks through $122$ win and rank $123$ ties. These are not thresholds for every arbitrary combination of ranks or list weights. At $m=100,\kappa=60$, the within-list top/bottom vote ratio is $(\kappa+m)/(\kappa+1)=160/61\approx2.622951$. At $\kappa=0$ it is $100$, so list-head rank differences are much stronger, but agreement still matters. For $\kappa=5$, two-way equal-rank agreement ties a solo top hit at rank seven, and the within-list ratio is $105/6=17.5$. These describe truncated list weights, not confidence or the expected benefit of another retriever.