ColBERT: Late Interaction and Multi-Vector Retrieval

Chapter 1: The Interaction Spectrum

Every neural retrieval system answers the same two questions, and its entire cost profile falls out of the answers.

Question one: how rich is the representation? One vector per document, or one per token, or no fixed representation at all because the document is re-read every time?

Question two: how late does the query meet the document? Do they meet inside the transformer, with every query token attending to every document token through twelve layers? Or do they meet at the very end, in a similarity computation over frozen vectors?

Those two questions are really one question, because a representation you can precompute is a representation the query did not participate in. That is the whole tension. The ColBERT paper draws it as four boxes; we will walk them in order of decreasing cost.

Level 1 — the cross-encoder (all-to-all interaction)

Concatenate query and passage into one sequence, feed it to BERT, read a relevance score off the [CLS] vector. Formally:

Every query token attends to every document token in every layer. If the passage says "Challenger Deep" and the query says "how deep", the attention mechanism can build a representation of the relationship between them: not just that both mention depth, but that this passage answers this question. Nothing in a precomputed representation can do that, because the relationship did not exist at index time.

The cost is brutal and it is easy to see why. Let us count it, because the number is the whole argument. BERT-base has about 110M parameters, and a forward pass costs roughly two floating-point operations per parameter per token (one multiply, one add):

Multiply by 1,000 candidate passages and you get 5.6 × 10¹³ FLOPs per query. The paper measures 97 TFLOPs, which is the same order — the difference is attention's quadratic term and the exact sequence length. On the hardware of 2020 that came out at 10,700 ms per query. You can run this offline. You cannot run it in a search box.

Where the cross-encoder's cost actually goes

The two-FLOPs-per-parameter rule is a shortcut, and it is worth spending five minutes doing the count properly, because the answer contradicts what most people assume.

BERT-base has d = 768, twelve layers, and a feed-forward inner size of 4d = 3,072. Per token per layer, the matrix multiplies are:

Then the part everyone worries about — attention itself, which is quadratic in sequence length. Each token attends to all L tokens, computing a score (d MACs) and a weighted sum (d MACs):

Divide: 393,216 / (7,077,888 + 393,216) = 5.3%. At 256 tokens, attention is a twentieth of the cost. The other nineteen twentieths are ordinary dense layers being applied once per token per layer.

Notice this is less than the 56 GFLOPs the rule of thumb gave, and the gap is instructive: of BERT-base's 110M parameters, about 24M are the wordpiece embedding table, which is a lookup rather than a multiply. Only the 85M encoder parameters do arithmetic. Rules of thumb that count all parameters over-charge every model with a large vocabulary.

Level 2 — the single-vector bi-encoder (no interaction)

The opposite extreme. Two independent encoders, one per side. Every passage in the corpus is encoded once, offline, into a single vector. At query time you encode the query once and take dot products.

This is DPR (Dense Passage Retrieval, Karpukhin et al. 2020) and its many descendants. The query-time cost per passage is one 768-dimensional dot product: 1,536 FLOPs. Against the cross-encoder's 56 GFLOPs, that is a factor of about 36 million. And because the score is a plain inner product, you can hand the whole corpus to an approximate nearest neighbour index and never touch most of it.

What you gave up is Chapter 0's whole story: the passage was summarised before the question arrived.

Level 3 — late interaction (the middle)

Here is the move. Encode both sides independently — so the document side is still precomputable, still offline, still indexable. But do not pool. Keep the full matrix of token vectors. Then, at query time, let every query token look at every document token — not through attention, which would require running a transformer, but through a plain similarity computation over the frozen vectors.

That is the entire ColBERT scoring function, and Chapter 2 does nothing but unpack it. Read it in English: for each query token, find the document token it matches best, and add up those best matches.

The word "late" now has a precise meaning. Interaction between query and document is deferred until after both have been encoded — so it can happen on cheap frozen vectors, and the expensive part (encoding the corpus) happens once, offline, forever.

Level 2.5 — the few-vector middle, and why it is not enough

Between one vector and one per token there is an obvious compromise nobody should skip past: store a handful. Two 2020 papers did exactly that.

Poly-encoders (Humeau et al.) keep m learned "code" vectors per query context and attend over the document representation; ME-BERT keeps m = 8 vectors per document, taken from the first m token positions, and scores with a max over the eight. Both sit between DPR and ColBERT on every axis, and both improve on DPR.

So why did the field keep going to n vectors? Because m vectors do not remove the decision, they shrink it. Something still has to choose which 8 summaries to keep, at index time, without the query. ME-BERT's choice — the first 8 positions — is arbitrary and systematically wrong for any passage whose key fact appears late. A learned clustering is better and is still a frozen commitment: the clustering objective was fitted to a query distribution, and Chapter 9 is about what happens when the distribution moves.

The row that matters is "when". Every design above the last one has a step where information is thrown away in ignorance of the query. n vectors is the unique point on this spectrum where that step does not exist — which is why the interesting engineering question stopped being "how many vectors" and became "how cheaply can we store all of them".

Level 4 — the query-document interaction models that came before

For completeness, and because it explains why late interaction felt surprising in 2020: there was already a family of models — KNRM, ConvKNRM, DRMM — that built a query-document similarity matrix and ran a small neural network over it. Structurally, that is late interaction. What they lacked was contextualized embeddings: their token vectors were static word2vec-style vectors, so "deep" had one vector regardless of context. Their MS MARCO numbers sat around 0.198 to 0.290 MRR@10. ColBERT is that architecture with BERT's contextual embeddings dropped in, plus the engineering to make it a retriever rather than a re-ranker.

The spectrum, with numbers attached

The column that should stop you is the ColBERT one. It is not the best on any single row. It is second-best on every row, and that turns out to be a very rare and very valuable place to stand.

Look at the middle panel in "compare all three". The bold edges — the ones MaxSim actually keeps — number exactly one per query token. Everything else in that matrix is computed and then discarded by the max. That observation is what makes Chapter 6's pruning possible: if you could guess which edges will win, you would not have to compute the rest.

The engineering consequence nobody states out loud

There is a practical asymmetry that decides which of these you can actually deploy, and it is not quality and it is not latency. It is where the cost lands.

Offline cost is the cost you can throw hardware at overnight. Online cost is the cost you pay in front of a user with a 200-millisecond budget. Moving work from the second column to the first is the single most valuable move in systems design, and late interaction is a very pure instance of it: it moves twelve transformer layers offline and leaves one matrix multiply online.

Three questions that classify any retrieval architecture

Every system in this lesson — and every system published since — is fully determined by three answers. It is worth carrying the checklist, because it turns a confusing zoo of acronyms into three yes-or-no questions.

Ask them of anything new and you will know roughly what its BEIR number looks like before you read the table. A method whose answer to question 3 is "no" is buying quality from its training distribution and will hand some of it back when the distribution changes.

Chapter 2: MaxSim, By Hand

Here is the scoring function again. By the end of this chapter you will have computed every number in it with a calculator, and you will know why each design choice inside it is the way it is.

Three operations, in order: a matrix of dot products, a maximum along each row, and a sum of those maxima. Call it MaxSim — the paper's name for the per-query-token maximum-similarity operator.

Setting up a case we can compute completely

Real ColBERT embeddings are 128-dimensional, which is not something you can multiply on paper. So we shrink to four dimensions and give each one a name. This is a fiction — real embedding dimensions have no names — but every operation we perform is the real one, and the conclusions transfer.

The query is "how deep is the mariana trench". After the tokenizer, three tokens carry content. Their (unnormalised) encoder outputs:

Read those and check they make sense. "deep" is almost pure depth with a little water and a little number-ness (it appears next to measurements). "mariana" is overwhelmingly a place name. "trench" straddles all three: it is a depth feature, it is oceanic, and it is part of a proper noun.

Document A is the passage we want: "Challenger Deep plunges 10935 metres". Five tokens:

Notice the contextualization already at work in the numbers. The document's "deep" is not the same vector as the query's "deep": in "Challenger Deep" it has picked up place-name mass (dimension 3 went from 0 to 2), because BERT read the capital letter and the preceding word. That is the "C" in ColBERT doing its job before we have computed a single similarity.

Step 1 — the similarity matrix, one cell at a time

ColBERT normalises every embedding to unit length, so the dot product is the cosine. We will do it the long way — raw dot product, then divide by the two lengths — so you can see both halves.

Cell (1,1): q₁ "deep" against a₁ "challenger".

Cell (1,3): q₁ "deep" against a₃ "plunges". This is the interesting one.

Stop and appreciate what just happened. The query word "deep" matched the document word "plunges" at 0.9925 — higher than it matched the document's own literal "deep" (0.9679, computed next). There is no string overlap between "deep" and "plunges" at all. BM25 would score that pair exactly zero. This one number is the entire case for neural retrieval, and it is happening at the level of a single token pair, where you can see it.

Cell (1,2): q₁ "deep" against a₂ "deep".

The identical surface form scores lower than the paraphrase, because context pulled the document's "deep" toward the place name. Late interaction does not reward string equality. It rewards being the right vector.

Cell (2,1): q₂ "mariana" against a₁ "challenger".

Two different proper nouns naming the same place, matched at 0.957. Again, no lexical overlap.

Grinding through the remaining ten cells the same way gives the full 3 × 5 matrix. Every entry below was produced by exactly the arithmetic shown above.

Step 2 — the row maxima

For each query token, scan its row and keep the single largest entry. Row 1's largest is 0.9925 at "plunges". Row 2's is 0.9571 at "challenger". Row 3's is 0.9322, also at "challenger".

Note that row 2 and row 3 both chose column 1. Nothing forbids that — MaxSim is not a matching, it is an independent argmax per row. Two query tokens are allowed to be satisfied by the same document token, and often are, because a proper noun carries several query concepts at once.

Step 3 — the sum

Three query tokens, so the maximum possible score is 3.0. We are at 2.88, or 96% of a perfect match. The passage answers the question, and the score says so.

The control: a passage that is topically close but says nothing

A scoring function that gives a good passage a high number is not yet evidence of anything. It has to give a bad passage a lower one. So here is document B, the kind of passage that lives all over the web: "Pacific waters are cold below". Same length, same topic area, zero information.

One cell in full, so you can check the rest: (1,5): q₁ "deep" against b₅ "below".

A wins by 0.282. The margin comes almost entirely from row 2 — "mariana" found a 0.957 match in A and only a 0.772 match in B — which is the correct reason. The specific entity is what distinguishes the two passages, and MaxSim's row structure is what let that single piece of evidence show up in the total.

Now compare against the two obvious alternatives

Why max? Why not the sum of the whole matrix, or the mean? These are not rhetorical questions; they are ablations, and the toy is small enough that we can run them.

Alternative 1: sum every cell (SumSim). Add all fifteen entries.

The ranking inverts. The vacuous passage wins by a full point. And the reason is exactly visible in the numbers: B's cells are uniformly mediocre — nothing below 0.24, lots around 0.7 — while A's are polarised, with four cells under 0.25 dragging its total down. Summing rewards diffuse topical similarity. Taking the max rewards specific evidence and ignores everything else.

This is worth naming, because it is the single most common failure of naive similarity aggregation: a document that is vaguely about everything beats a document that is precisely about one thing. The max operator is what makes the score insensitive to how much irrelevant material a passage contains — which is Chapter 0's dilution problem, solved at the operator level rather than by chunking.

Alternative 2: pool both sides and take one cosine. Average the three normalised query vectors, average the five normalised document vectors, renormalise, and take a single dot product. The arithmetic is long but mechanical; the results are:

Pooling gets the ranking right here — A still wins. But look at the margin. Under MaxSim the gap is 0.282 on a scale where A scores 2.882, a relative margin of 9.8%. Under pooling the gap is 0.038 on a scale where A scores 0.801, a relative margin of 4.7%. Pooling did not destroy the signal; it halved it. Halve a signal enough times in a corpus of nine million passages and some of those nine million will slip above the right answer by noise alone.

Why the max is also the right thing for learning

There is a second argument for max that has nothing to do with ranking quality, and it is about gradients.

Differentiate the max with respect to the document embeddings. The maximum of a set is a piecewise-linear function: its derivative is 1 with respect to the winning element and exactly 0 with respect to all the others. So during training, for query token i, gradient flows to exactly one document token — the argmax — and to nothing else.

The consequence is a hard assignment: training pushes each query term toward its single best-matching document term and leaves the rest of the document alone. That is structurally the same thing an inverted index does when it looks up one posting list and ignores the other thirty thousand. MaxSim is a soft, learned, differentiable version of exact term matching — and Chapter 9 will argue that this inductive bias is precisely why it survives a change of domain.

Play with the matrix

The realization: what this looks like in tensors

Everything above is one matrix multiply, one reduction, and one sum. Here it is with shapes, because a formula you cannot allocate memory for is not yet understood.

python — MaxSim, exactly as scoredimport torch

# Eq: query embeddings, one row per query position, L2-normalised
Eq = model.encode_query("how deep is the mariana trench")   # (32, 128)

# Ed: document embeddings, one row per surviving document token
Ed = index.lookup(doc_id)                                 # (n, 128), n ~ 73

S     = Eq @ Ed.T                                        # (32, n)  every pair
best  = S.max(dim=1).values                              # (32,)    one per query row
score = best.sum()                                        # ()       a scalar

Three lines. Now count the work. The matrix multiply is 32 × n × 128 multiply-accumulates, which is two FLOPs each:

Over 1,000 candidate documents that is 0.6 GFLOPs. Hold that number next to the cross-encoder's 56 GFLOPs per document, or 56 TFLOPs for the same 1,000. The ratio is about 10⁵.

And here is the detail that reorders your intuition about where the time goes. Encoding the query itself — one BERT-base forward pass over 32 tokens — costs roughly 2 × 110×10⁶ × 32 ≈ 7 GFLOPs. That is more than ten times the cost of scoring all thousand documents. In a ColBERT re-ranker, the expensive part of the query is the query. The paper's measured figure of about 7 × 10⁹ FLOPs per query is essentially the query encoder alone, with MaxSim as a rounding error on top.

Batching it properly

One more realization detail, because it is where naive implementations lose their speed. Candidate documents have different lengths, so you cannot stack them into a clean (B, n, 128) tensor without padding, and padding a 20-token passage out to 180 wastes 89% of the multiply. Two production patterns:

The flat version turns a thousand small matrix multiplies into one large one, which is the difference between 5% and 80% GPU utilisation. It also means the intermediate S is a single (32, T) tensor with T ≈ 73,000 for a thousand candidates — about 9 MB in fp32, which fits comfortably in cache-friendly territory.

Chapter 3: Marks, Masks, and 128 Dimensions

MaxSim is four lines of tensor code. Everything else in the ColBERT paper is the machinery that produces the two matrices it consumes — and every piece of that machinery is a decision with a measurable consequence. This chapter walks them in the order the data flows.

One BERT, two roles

The first surprise: ColBERT does not use two encoders. It uses one BERT whose parameters are shared between the query side and the document side. This halves the parameter count and, more importantly, guarantees the two sides land in the same space from initialisation onward — you are not asking two independently-initialised networks to negotiate a common coordinate system through gradient descent alone.

But shared weights create an immediate problem. If the same network encodes both sides, then the string "mariana trench" produces the identical vector whether it arrived as a question or as a passage. And those two situations call for different behaviour: a query token should behave like a request for evidence; a document token should behave like a piece of evidence.

The fix is two special tokens, [Q] and [D], prepended right after [CLS]. Implementationally they are two of BERT's unused vocabulary slots ([unused0] and [unused1]), so no vocabulary surgery is needed — they are ordinary embedding rows that were never trained and are now given a job.

Because self-attention is global, the marker at position 1 is visible to every other position in every layer. It acts as a mode switch that conditions all 32 or 180 output vectors. One token, two behaviours, zero extra parameters beyond a single 768-dimensional embedding row.

Query augmentation: padding with [MASK] on purpose

Now the strangest design choice in the paper, and the one worth the most thought.

Queries are short. "how deep is the mariana trench" is seven wordpieces. ColBERT pads every query to a fixed N_q = 32 positions — and pads not with a neutral [PAD] token that gets masked out, but with [MASK], the token BERT was pretrained to fill in.

Those mask positions are not discarded. They go through BERT, get contextualized, get projected, get normalised, and take part in MaxSim exactly like real query tokens.

The paper calls this query augmentation and its ablation removes it: MRR@10 falls by roughly one and a half points. For a change that adds no parameters and costs only a longer (but fixed) query tensor, that is an excellent trade.

There is a second, quieter benefit. Because N_q is fixed at 32, the MaxSim sum always has exactly 32 terms — for a three-word query and for a twenty-word query alike. Scores are therefore on a comparable scale across queries, which matters when you set thresholds or compare a query's top score against a floor. Variable-length sums would make every threshold query-dependent.

And a third: the mask positions give the model somewhere to put re-weighting behaviour. If a query term is unimportant, the model can learn to make its vector short… except it cannot, because everything is normalised to unit length. What it can do instead is make the vector point somewhere that matches almost nothing, so its row max stays low. The masks give it 25 extra rows to spend on whatever the training signal says is useful.

What a [MASK] row actually converges to

"BERT fills in the blank" is a story, not a mechanism. Here is the mechanism, in one paragraph of attention.

At layer 1 the vector at a mask position is the [MASK] input embedding plus its positional embedding — identical content at every mask slot, differing only by position. Self-attention then lets that position read every real query token. Because the mask's own content carries no information, its attention output is dominated by whatever the query tokens contribute, so by the final layer the vector is a function of the query context and the slot index. Twenty-five slots, one shared context, twenty-five different positional starting points: the model has room to place twenty-five distinct query-conditioned probes.

What it uses them for is decided by the loss, and the loss only ever says "make relevant passages score higher". So the training pressure on a mask row is: point somewhere that matches good passages and not bad ones. Empirically the rows behave like soft expansion terms — near a plausible related word — and like importance re-weighting, since a row that points into empty space contributes a low row max and effectively abstains.

Why 32 and 180, and what those constants really are

Both limits are fitted to MS MARCO and both become the model's failure mode elsewhere, so it is worth knowing what they were fitted to.

MS MARCO queries are Bing search queries: about six words, or roughly seven to eight wordpieces, with a long thin tail. N_q = 32 covers essentially all of them with room for expansion. MS MARCO passages average around 56 words, or roughly 76 wordpieces; 180 covers the overwhelming majority, and anything longer is truncated.

Neither number is a law. Both are the shape of one dataset, hardened into an architecture. When you deploy late interaction on documents that are not web passages, these are the first two things to change and the last two things anyone thinks to check.

One encoder or two?

DPR uses two entirely separate BERTs — one for questions, one for passages — on the argument that questions and passages are different kinds of text and deserve different parameters. ColBERT shares one. Both choices are defensible and the tradeoff is worth naming.

The last row is the one that bites in production. If your query encoder and your document encoder are separate artefacts, then re-training one and not the other silently corrupts every score, and nothing crashes. Sharing weights makes that mistake unrepresentable.

Counting the model

Before we look at storage again, count what has to be loaded at query time:

That is the entire model. Everything else — the 20 GiB index, the 134 MB centroid table — is data, not weights. It is worth internalising that ratio: the artefact that took a week of GPUs to train is a hundredth the size of the artefact that took an afternoon to build from it.

Punctuation filtering

On the document side, ColBERT deletes the embeddings of punctuation symbols after encoding. Not before — after. The punctuation still participates in BERT's attention (a full stop is real evidence about sentence boundaries), it just does not get stored in the index or offered to MaxSim.

Two reasons, one economic and one about failure modes.

The economic one: punctuation is roughly 7% of wordpiece tokens in MS MARCO passages. Deleting it deletes 7% of the index, which is measured in tens of gigabytes. The paper reports no measurable quality loss.

The failure-mode one is more interesting. Remember that a query's 25 [MASK] rows are looking for something to match. A comma's embedding is a low-information vector that sits near the centre of the space, so it has middling similarity with almost everything — and middling similarity to 25 mask rows adds up. Filtering punctuation removes a class of cheap, meaningless matches that MaxSim would otherwise happily bank.

The projection down to 128

BERT-base emits 768 numbers per token. ColBERT puts a single linear layer on top — no bias in the usual implementation, no activation function — that maps 768 to m = 128, then L2-normalises the result.

Two things are happening in that one line and they are worth separating.

The projection is about storage. Run the arithmetic. At fp16, one 768-dimensional vector costs 1,536 bytes; one 128-dimensional vector costs 256 bytes. MS MARCO's 8.8 million passages produce roughly 6.4 × 10⁸ token embeddings after punctuation filtering (about 73 per passage). So:

916 gigabytes is not an index, it is a decision to abandon the project. 153 GiB is expensive but survivable on 2020 hardware, and Chapter 5 gets it to 20. The projection is what made the method exist.

The normalisation is about the scoring function. Once every row has unit length, the dot product equals the cosine, so every cell of the similarity matrix lies in [−1, 1] and every MaxSim score lies in [−32, 32]. That bounding does three jobs: it stops long-vector documents from winning by magnitude (the exact failure mode that "vector norms encode frequency" would otherwise cause), it makes the max operator compare like with like, and — the one nobody mentions until they need it — it makes quantization tractable, because you know in advance the range every number lives in. Chapter 5 depends on that.

The paper ablates m. The shape of the result is that quality degrades gracefully — roughly 0.349 MRR@10 at m = 128, still around 0.343 at m = 48, around 0.339 at m = 24 — while storage falls linearly. Read that carefully, because it sets up the next design generation: dimension reduction buys storage at a real, if small, quality cost. Quantization, as we will see, buys storage at almost no quality cost. Given the choice, you quantize.

Walk the whole thing in shapes

python — the full encode path, with every shape# ---------- OFFLINE, once per passage ----------
ids  = tokenizer("[D] Challenger Deep plunges 10935 metres")   # (n0,)   n0 = 9
H    = bert(ids)                                                # (n0, 768)
E    = H @ W                                                    # (n0, 128)
E    = E / E.norm(dim=-1, keepdim=True)                      # (n0, 128) unit rows
E    = E[~is_punctuation(ids)]                                 # (n, 128)  n = 8
index.put(doc_id, E.half())                                   # 8 x 256 B = 2,048 B

# ---------- ONLINE, once per query ----------
ids  = tokenizer("[Q] how deep is the mariana trench")          # (7,)
ids  = pad(ids, 32, value=MASK_ID)                              # (32,)  25 [MASK]s appended
Eq   = normalize(bert(ids) @ W)                                # (32, 128)

# ---------- SCORING, per candidate ----------
S     = Eq @ Ed.T                                              # (32, n)
score = S.max(dim=1).values.sum()                             # ()

Two numbers from that listing are worth memorising because they anchor everything downstream. A query is 32 × 128 = 4,096 floats, or 8 KB in fp16 — small enough to broadcast to every shard of a distributed index. A passage is n × 128, about 2 KB in fp16 for a short one and 18 KB for a 180-token one. Multiply the second by the size of your corpus and you have Chapter 5's problem.

What the design does not include, and why

Chapter 4: Triples, Then a Teacher

We have an architecture that produces two matrices and a scoring function that turns them into a number. Nothing so far says what those numbers should be. This chapter is about the training signal — and it is the single place where ColBERTv2 differs most from ColBERT, because the architecture between the two versions is unchanged. Same markers, same masks, same 128 dimensions, same MaxSim. What changed was the supervision and the storage. That fact is itself a result: it says the 2020 architecture was not the bottleneck.

Version 1: triples and a two-way softmax

ColBERT trains on MS MARCO's official triples: a query q, a passage d⁺ that a human marked relevant, and a passage d⁻ sampled from BM25's top-1000 for that query. The loss is a softmax cross-entropy over exactly two scores:

Work an instance. Suppose the current model scores the positive at S⁺ = 21.4 and the negative at S⁻ = 20.9 (remember these are sums of up to 32 cosines, so the natural scale is tens, not units).

Notice we never had to exponentiate 21.4 — only the difference matters, which is why implementations subtract the max before exponentiating. Notice also what the loss wants: it is minimised as the gap S⁺ − S⁻ goes to infinity. It has an opinion about order and no opinion at all about how much better the positive should be.

In-batch negatives: free supervision from the batch

One triple gives one negative. But if you are already encoding a batch of B queries and B positives on a GPU, you can compute all B × B scores for almost nothing — the extra work is the MaxSim matrices, which Chapter 2 showed are a rounding error next to the encoder passes.

Every off-diagonal cell is a query paired with some other query's positive: a plausible negative, free. The loss becomes a B-way softmax per row, with the diagonal as the target.

For B = 64 you get 63 negatives per query instead of 1, at a marginal cost of computing a 64 × 64 grid of MaxSim scores. This is the same trick CLIP uses on image-text pairs, and it has the same limitation: a random other query's positive is usually easy to reject. If the batch contains "how deep is the mariana trench" and "how to bake sourdough", distinguishing them teaches the model almost nothing, because it already can.

Let us make "teaches almost nothing" quantitative, because it is the hinge of the whole chapter.

Working an in-batch loss by hand, twice

Take B = 3 and a score grid where each query strongly prefers its own positive — the easy-negative regime:

Row 1, subtracting the row max of 22.1 before exponentiating:

Row 2, max 21.7:

Row 3, max 22.4:

Now change one number. Make query 1's hardest negative genuinely competitive — S₁₂ = 22.0 instead of 19.4, a passage that nearly answers the question:

One row's loss went from 0.080 to 0.653, an eightfold increase, from a single hard negative. The gradient magnitude follows: in a softmax cross-entropy the gradient with respect to the score of negative j is exactly p_ij, so a negative the model assigns 0.067 probability contributes a hundredth of the push that one at 0.47 does.

The problem with hard negatives: most of them are not negative

Mine hard negatives from BM25's or your own model's top-k and you will collect passages that look relevant. Some of them look relevant because they are.

MS MARCO's annotation protocol produced roughly one marked-relevant passage per query out of a corpus of 8.8 million. That is not a claim that only one passage answers the question — it is an artefact of how much a human was asked to read. RocketQA (Qu et al., 2021) made this concrete by re-annotating top-retrieved unlabelled passages and finding a large share of them genuinely relevant; their fix was to run a cross-encoder over candidate negatives and throw out the ones it scored highly.

So the pairwise loss, applied to mined negatives, is doing something worse than being uninformative. It is asserting a falsehood. Take a query with two genuinely good answers, A and B, where A happens to be the labelled one. The loss says: drive p(B) toward zero. The model complies. It learns to distinguish a correct answer from a correct answer.

Version 2's answer: let a cross-encoder grade the exam

ColBERTv2's supervision is knowledge distillation from a cross-encoder. Not the 10.7-second one from Chapter 1 — a small MiniLM cross-encoder, which is still far too slow to serve but perfectly fine to run offline over a training set.

The loop, in order:

Working the KL divergence by hand

KL divergence — short for Kullback–Leibler — measures how much a distribution q differs from a reference distribution p. Written out:

Shrink the 64 passages to 4 so we can compute every number. Teacher scores: 8.2, 5.1, 4.7, 1.3. Subtract the max and exponentiate:

Student MaxSim scores on the same four: 21.4, 20.9, 18.6, 15.2.

Now term by term. This is where the shape of the signal becomes visible.

Two observations that people trip over. First, individual terms can be negative — only the total is guaranteed non-negative, and it is zero only when the two distributions are identical. Second, the term sizes are weighted by p, the teacher's belief. The teacher is confident about passage 1 and its disagreement there dominates the loss. It barely cares about passage 4, and neither does the gradient.

An aside: why ColBERT has no temperature and CLIP needs one

If you have met contrastive learning through CLIP or SimCSE you will be waiting for a temperature — a learned scalar τ that divides the similarities before the softmax. ColBERT does not have one, and the reason is a nice piece of dimensional reasoning.

A single-vector model's score is one cosine. Two plausible passages might differ by 0.03 — say 0.81 versus 0.78. Feed that straight into a softmax and you get probabilities of 0.5075 and 0.4925: essentially no signal, and a loss that barely moves. Hence a temperature, typically 1/τ between 20 and 100, which turns 0.03 into a usable 0.6 to 3.0 logit gap.

MaxSim sums 32 cosines. Two passages that differ by 0.03 per matching token differ by up to 0.96 in the total, and in practice good and mediocre passages separate by several points on a scale that runs to 32. Check what that does to a softmax:

The score is already on a scale where differences of interest are order-one, so the identity function is a perfectly good temperature. Summing over the query axis did the sharpening that CLIP has to learn a parameter for. It is a small thing, and it is the kind of small thing that saves a hyperparameter sweep.

The remaining half of the loss is the in-batch cross-entropy from earlier, kept because it supplies negatives from outside the 64-passage neighbourhood — the distillation term teaches fine ranking among near-misses, the in-batch term keeps the model from collapsing everything unrelated into the same region.

Run the pairwise loss for twenty steps and watch passage 2's bar go to the floor while the teacher's bar for it stays at 0.042. That gap is a model being trained to believe something false. Then run distillation and watch the student's whole shape settle onto the teacher's.

What it bought, in numbers

Read the ColBERT rows together: identical architecture, +3.7 MRR@10. Then read the RocketQAv2 row: a single-vector model with equally careful supervision reaches 0.388, only 0.9 behind. In-domain, on the dataset everybody trains on, careful supervision matters more than representation richness. Hold that thought until Chapter 9, where the two models go somewhere they have never been and the ordering changes.

The realization: what the training step actually costs

python — one ColBERTv2 training step, with shapes# q: B queries; D: B x w candidate passages, w = 64 per query
Eq = encode_query(q)                       # (B, 32, 128)
Ed = encode_doc(D.flatten())                # (B*w, n, 128)

# MaxSim for every (query, its own 64 candidates) pair
S  = torch.einsum('bqh,bwdh->bwqd', Eq, Ed)  # (B, w, 32, n)
S  = S.max(dim=-1).values.sum(dim=-1)      # (B, w) student scores

# teacher scores were precomputed offline, once
p  = torch.softmax(teacher_scores, dim=-1)  # (B, w)
loss_kd = torch.nn.functional.kl_div(
              torch.log_softmax(S, dim=-1), p,
              reduction='batchmean')

# in-batch: every query against every other query's positive
S_ib = torch.einsum('bqh,cdh->bcqd', Eq, Ed[:, 0])
S_ib = S_ib.max(dim=-1).values.sum(dim=-1)   # (B, B)
loss_ib = torch.nn.functional.cross_entropy(S_ib, torch.arange(B))

loss = loss_kd + loss_ib

The teacher never appears in that step. Its 64 scores per query were computed once, offline, and cached — which is what makes distillation from an expensive model affordable. You pay a cross-encoder's price on the training set (hundreds of thousands of queries) instead of on the corpus (millions of passages) or the traffic (billions of queries).

Chapter 5: Residual Compression

Time to confront the bill. ColBERT stores one vector per token. That is the source of everything good about it and the entire reason it was, for two years, a method people admired and did not deploy.

The bill, computed from scratch

MS MARCO's passage collection has 8.8 million passages. After wordpiece tokenization and punctuation filtering, they average about 73 stored tokens each. So:

Six hundred forty million vectors. Each is 128 dimensions. At 16-bit floats:

The paper reports 154 GiB, so our arithmetic is honest. Now put that number in context. A 2020-era server with 192 GB of RAM can hold it and nothing else. Sharding it across machines is possible and it means your retrieval index costs more in hardware than your language model does. Meanwhile BM25's index for the same corpus is under a gigabyte.

The observation that makes compression possible

Here is the empirical fact ColBERTv2 leans on: the token embeddings are not spread uniformly over the 128-dimensional unit sphere. They cluster, tightly, into regions that correspond to specific token senses. The vector for "deep" in an oceanography passage sits very near the vector for "deep" in ten thousand other oceanography passages. Contextualization moves it a little. It does not move it far.

That is not surprising once you say it out loud. There are only about 30,000 wordpieces in BERT's vocabulary, and context perturbs each one within a neighbourhood. 640 million vectors drawn from roughly 30,000 sense-clusters means each cluster holds tens of thousands of near-duplicates. Storing each of them at full precision is storing the same information tens of thousands of times.

The scheme: a centroid plus a small correction

Run k-means over a sample of the corpus embeddings to get C centroids. Then for every embedding v:

How many centroids? ColBERT's implementation scales the count with the square root of the collection: roughly 16√N_emb, rounded up to a power of two. For our corpus:

Now the storage arithmetic, all the way down

Against 153 GiB, that is a factor of

and it lands right on the paper's reported figure of about 20 GiB and its claimed 6–10× range. Run the same arithmetic at b = 1 bit per dimension:

And now the comparison that should genuinely surprise you. Per passage:

A compressed multi-vector index is smaller than an uncompressed single-vector index, and within 1.6× of a half-precision one. The thing everybody knew was too big to deploy stopped being too big to deploy, and the architecture never changed.

Why two bits is enough — the error budget

Two bits per dimension sounds recklessly small. Reason about it rather than trusting it.

What is being quantized is not the embedding, it is the residual. Suppose (representatively — the exact figures depend on the corpus) that in a given dimension the raw embedding values have a standard deviation around 0.09, while the residuals after centroid subtraction have a standard deviation around 0.02. Four buckets placed at the residual quantiles reduce the per-dimension reconstruction error to roughly 0.008.

Across 128 dimensions the squared error accumulates:

Now convert that into what actually matters — the change in a similarity. For two unit vectors, the relation between distance and cosine is exact:

So each stored embedding sits about 0.996 cosine from its true self. Each cell of the similarity matrix is perturbed by a few thousandths. Summed over 32 query rows, the MaxSim score wobbles by roughly 32 × 0.004 ≈ 0.13, on scores that live around 20 — well under 1%.

And crucially the perturbation is unbiased and shared: every document is degraded by about the same amount, so the ranking is nearly untouched. Quantization noise only flips a pair when their true scores were within 0.13 of each other, in which case you were choosing between two nearly-equivalent passages anyway.

Doing the quantizer properly

The 0.008 above was an estimate. The bucket boundaries are not arbitrary, and the exact answer is a solved problem worth knowing, because it tells you precisely what the second bit buys.

Residuals in a given dimension are close to zero-mean Gaussian with standard deviation σ ≈ 0.02. With b = 2 bits you get four reconstruction levels, and the optimal placement is the classical Lloyd–Max quantizer: boundaries at the conditional-mean midpoints, levels at the conditional means of each region. For a Gaussian, the equiprobable boundaries sit at the quartiles:

and the reconstruction levels are the conditional means of the four regions. For the outer regions, using the standard normal density φ:

So the four stored values per dimension are −0.0254, −0.0065, +0.0065, +0.0254 — and the two bits say which. The distortion of the optimal 4-level Gaussian quantizer is a tabulated constant, 0.1175σ², giving a root-mean-square error of

slightly better than our rough 0.008. Propagate it through the 128 dimensions and the cosine relation:

Now run the same machinery at b = 1. Two levels, the optimal Gaussian one-bit quantizer has distortion (1 − 2/π)σ² = 0.3634σ²:

Read down the fidelity column. The second bit cuts the squared error by 3.1× for 1.9× the space, and that buys a visible point of MRR. Bits three and four cut it a further 12× for another 1.9× the space and buy nothing measurable, because at cosine 0.997 the quantization error is already an order of magnitude below the score differences the ranking has to resolve. Two bits is not a compromise between one and four. It is the point where the curve goes flat.

The other half of the bill: building the index

Compression is not free at index time, and the arithmetic is worth seeing because it decides how often you can afford to re-index.

Assigning every embedding to its nearest centroid is, naively, a matrix multiply of 6.42×10⁸ vectors against 524,288 centroids in 128 dimensions:

On an accelerator sustaining 100 TFLOP/s that is about 860 seconds — fourteen minutes of pure arithmetic, which is astonishingly cheap for what it is. In practice it takes longer, because at these shapes the bottleneck is memory bandwidth rather than multipliers, and because the k-means itself must run first (on a sample of a few million embeddings, not the full set — centroids estimated from a sample are statistically indistinguishable from centroids estimated from everything).

The real cost of indexing is the part that is not the compression: one BERT forward pass over all 8.8 million passages. At 45.9 GFLOPs per 256-token passage that is 4×10¹⁷ FLOPs, an order of magnitude more than the clustering. Compression is a rounding error on an indexing job you were already paying for.

Budget it yourself

Push the document count to 100 million and watch every uncompressed bar leave the chart. Push tokens per document to 180 — ColBERT's truncation limit — and watch how much of your budget is spent on long documents you probably should have chunked. The calculator is the design conversation.

What compression costs in quality

The paper's ablation is unglamorous and that is the point: 2-bit residuals cost a few tenths of an MRR point against uncompressed embeddings; 1-bit costs closer to a full point. Compare that against dimension reduction from Chapter 3, where going from 128 to 24 dimensions — a 5.3× storage saving — costs about a full point too.

The general lesson generalises well past this paper. When you need to shrink a learned representation, first ask what structure the representation already has. Dimension reduction throws away directions blindly. Residual coding exploits the fact that the vectors were clustered all along, so it pays for information you actually have rather than information you assumed was uniform.

Chapter 6: PLAID — Serving It Fast

A 20 GiB index fits in memory. That solves storage and leaves the other half of the deployment problem completely open: you still cannot run MaxSim against 8.8 million passages inside a search box.

Chapter 2 measured MaxSim at 0.6 MFLOPs per document. Against the whole corpus that is 5.3 TFLOPs per query — the wrong side of every latency budget, and that is before you decompress 640 million embeddings to do it. Retrieval has to be a funnel: cheap filters first, expensive scoring only on survivors.

ColBERT v1 built that funnel with an approximate nearest-neighbour index (faiss) over individual token embeddings: for each of the 32 query rows, find the k nearest document tokens, collect the passages those tokens belong to, then score those passages exactly. It worked — about 450 ms end-to-end per query — and it was awkward, because a general-purpose vector index knows nothing about the structure MaxSim actually has.

PLAID (Santhanam et al., 2022) is the engine written after that structure was understood. Its central realization is one sentence long, and it comes straight out of Chapter 5.

Stage 1 — candidate generation

The index keeps an inverted list per centroid: centroid t → the passages containing at least one token assigned to t. This is, structurally, an inverted index — except the "terms" are 524,288 learned clusters rather than 30,000 vocabulary items.

Encode the query into its (32, 128) matrix and multiply against the centroid table:

4.3 GFLOPs — the same order as encoding the query itself, and a millisecond or two of GPU time. For each query row take the top nprobe centroids (1 to 4, depending on how deep a result list you need) and union their passage lists. The result is a candidate set of roughly 10⁴ to 10⁵ passages out of 8.8 million: three orders of magnitude gone, using one matrix multiply.

Stage 2 — centroid interaction

Now score every candidate approximately. For candidate passage d, replace each of its token embeddings by its centroid and compute MaxSim:

Here is the trick that makes it nearly free: every quantity inside that expression has already been computed. E_qi · c_t is exactly cell (i, t) of the S_cent matrix from stage 1. Approximate scoring is a gather and a max over an existing table — no dot products at all, no memory reads of residual data.

Rank the candidates by the approximate score and keep the top ndocs. PLAID's published configuration uses ndocs = 256 for k = 10, 1024 for k = 100, 4096 for k = 1000.

Stage 3 — centroid pruning

A refinement that sounds minor and is not. Most of the 524,288 centroids are irrelevant to any given query — a query about ocean depth has essentially zero similarity to the centroids covering cooking, tax law, or Python syntax. PLAID computes, for each centroid, its maximum similarity to any of the 32 query rows, and discards every centroid below a threshold t_cs (around 0.4 to 0.5).

This routinely removes well over 90% of centroids from further consideration, which shrinks the gather in stage 2 by the same factor and shrinks the amount of index data that has to be touched at all. Pruned centroids contribute their similarity as a floor value rather than being read.

The safety argument is the same error budget as Chapter 5's. A centroid whose best query similarity is below 0.4 cannot become a row maximum, because real matches score 0.8 and up and the residual can only move a similarity by a few thousandths. Pruning is not a heuristic gamble; it is a bound.

Stage 4 — decompress and score exactly

The survivors — typically ndocs/4, so about 64 passages for a top-10 query — get the full treatment. Look up their compressed residuals, reconstruct v̂ = c_t + dequantize(r̂), renormalise, run the real MaxSim from Chapter 2, sort, return k.

Sixty-four passages at 0.6 MFLOPs each is 38 MFLOPs. Nothing. The expensive exact scoring, the thing the whole method is about, is the cheapest stage in the pipeline.

What each stage is actually load-bearing for

Four stages is a suspicious number — pipelines accrete stages the way codebases accrete flags. So delete each one in turn and see what breaks. This is the fastest way to understand why the design is the shape it is.

Read the last row carefully, because it is a general pattern in approximate systems. The approximation is used where it is cheap and its errors are averaged over thousands of candidates; it is not used at the very top of the ranking, where a single error is the answer the user sees. Approximate broadly, exact narrowly. Every well-built retrieval funnel does this, and most badly-built ones fail because they are approximate all the way to the top.

The real currency is memory traffic, not FLOPs

Chapter 2 established that MaxSim's arithmetic is nearly free. So if the arithmetic is free, what exactly is PLAID saving? Count bytes moved instead of operations performed, and the pipeline's shape suddenly makes sense.

Suppose stage 1 produces 40,000 candidate passages of 73 tokens each. Two ways to proceed:

Nine times less data moved, and the decompression step — which is pure memory-bound work, not something a bigger GPU fixes — runs on 0.16% as many embeddings. At a realistic 50 GB/s of effective random-access bandwidth, 105 MB is about 2 ms of pure streaming in the ideal case and considerably worse in the real one, because passage data is scattered across a 20 GiB array and every access is a cache miss.

This is why the stage ordering is what it is. The cheap stage is not cheap because it does less arithmetic. It is cheap because it reads a 4-byte integer per token instead of a 36-byte record, and because the thing it reads is an index into a 134 MB centroid table that sits comfortably in cache.

How this compares to the classical version of the same idea

Inverted-index search solved this problem decades ago with WAND and BlockMax-WAND: maintain an upper bound on the score any document in a block of postings could achieve, and skip the whole block when the bound falls below the current k-th best score. It is worth naming the difference precisely, because it is the one place PLAID gives something up.

PLAID's approximation is empirically almost free, but "almost" is the honest word and it is worth knowing which one you have. If you are building a system where a retrieval result must be reproducible and defensible — legal discovery, regulated search — the exactness column is not a footnote.

What to tune when you are over budget

What it delivered

The CPU column is the one that changed who could use this. 45× on a CPU means late interaction stopped requiring a GPU in the serving path, which for most teams is the difference between "interesting paper" and "thing we can put behind an API".

The realization: what a shard actually holds

python — the four stages, with the data each one touches# Loaded once, resident in RAM:
#   centroids   (524288, 128) fp16          -> 134 MB
#   codes       (642_000_000,) uint32       -> centroid id per embedding
#   residuals   (642_000_000, 32) uint8     -> 128 dims x 2 bits, packed
#   ivf         centroid -> passage id list -> the inverted index

Eq = encode_query(q)                                # (32, 128)
Sc = Eq @ centroids.T                              # (32, 524288)   4.3 GFLOPs

# STAGE 3 (applied first as a filter): centroid pruning
live = Sc.max(dim=0).values >= t_cs                 # ~5% of centroids survive

# STAGE 1: candidate generation
top  = Sc[:, live].topk(nprobe, dim=1).indices      # (32, nprobe)
cand = ivf.union(top)                                 # ~40,000 passage ids

# STAGE 2: centroid interaction - a GATHER, not a matmul
approx = segment_max_sum(Sc, codes[cand])            # (40000,) approximate scores
short  = approx.topk(ndocs).indices                   # 256 passages

# STAGE 4: decompress the few survivors and score exactly
Ed    = decompress(centroids[codes[short]], residuals[short])
final = maxsim(Eq, Ed).topk(k)                        # the answer

Look at what stage 2 is, in that listing. It is a gather over an already-computed table followed by a segmented max. There is no floating-point multiply anywhere in the stage that eliminates 99.4% of the candidates. That is the whole art of retrieval engineering: arrange things so the step that discards the most does the least.

Chapter 7: The Tradeoff Table

Seven chapters of mechanism. Now the engineering question: given a corpus, a latency budget, and a machine, which of these do you actually build? That question deserves real numbers, and real numbers need metrics you can compute rather than nod at. So we start by earning the vertical axis.

MRR@10, computed by hand

Mean Reciprocal Rank at 10 asks one question per query: where in your top ten did the first relevant document appear? Score it as 1 divided by that rank, or zero if it never appeared. Average over queries.

Five queries, with the first relevant document landing at ranks 1, 3, 2, 22, and 5:

Now translate the numbers we have been quoting. BM25's 0.187 on MS MARCO does not mean "18.7% correct". It means the average reciprocal rank is 0.187 — and since the reciprocal rank is at most 1, an MRR of 0.187 puts a hard ceiling of 18.7% on how often the right passage was ranked first. ColBERTv2's 0.397 raises that ceiling to 39.7%.

nDCG@10, computed by hand

MRR only looks at the first hit, which is wrong when several documents are relevant to different degrees. nDCG — Normalized Discounted Cumulative Gain — fixes both: it uses graded relevance and it discounts by position.

Suppose your top five results have relevance grades 3, 0, 2, 3, 1 on a 0–3 scale. Term by term:

To normalise, compute the DCG of the best possible ordering of the same grades — 3, 3, 2, 1, 0:

The exponential gain term is what makes nDCG useful for graded judgements: moving a grade-3 document from rank 4 to rank 2 is worth much more than moving a grade-1 document the same distance. BEIR, in Chapter 9, reports nDCG@10 because its eighteen datasets use graded relevance from many different annotation protocols and it needed one comparable number.

The third metric, which nobody publishes and everybody needs

Recall@k — the fraction of relevant documents that appear anywhere in the top k — is the metric that decides whether a first-stage retriever is usable in a pipeline. If you plan to re-rank the top 1,000 with a cross-encoder, then nothing outside those 1,000 can ever be recovered, so Recall@1000 is a hard ceiling on the entire system.

Compute one by hand so the number means something. Suppose across four queries the relevant documents found in the top 50 were 2 of 3, 1 of 1, 0 of 2, and 4 of 4:

Note the third query: a complete miss contributes a hard zero and drags the mean down by 0.25 on its own. Recall averages are dominated by total failures, which is exactly the right sensitivity for a first stage — a query where you retrieved nothing useful is a query the rest of the pipeline cannot save.

The Recall@1000 column is the one that changed pipelines. BM25 loses about 14% of answers before any neural model gets a look; ColBERTv2 loses under 2%. If your architecture is "cheap first stage, expensive re-ranker", the first stage's recall is your ceiling, and 0.857 versus 0.984 is a very expensive 12.7 points to leave on the table.

Everything on one page

Some numbers are approximate and depend on the exact checkpoint, hardware, and engine; the orders of magnitude are what the table is for. Read it column by column and the shape of the design space appears.

Storage column: a 20× spread from BM25 to ColBERTv2 and a 170× spread from BM25 to ColBERT v1. Compression collapsed the range, and that collapse is the reason late interaction stopped being exotic.

Latency column: two clusters, separated by two orders of magnitude. Everything precomputed sits at tens to hundreds of milliseconds. The cross-encoder sits alone at ten seconds. There is nothing in between, because there is nothing in between architecturally — either the corpus was encoded offline or it was not.

Quality columns: and here is the interesting disagreement. Ordered by MS MARCO MRR@10, the ranking is ColBERTv2 > SPLADE > ColBERT > cross-encoder > single vector > BM25. Ordered by BEIR average, it is ColBERTv2 ≈ SPLADE > cross-encoder > ColBERT > BM25 > single vector. BM25 moves from last to fifth and DPR falls to the bottom. Chapter 9 is entirely about why.

Cost, in units your finance team recognises

Storage per million documents, at the 73-tokens-per-document assumption, converted to a rough monthly RAM cost at commodity prices (call it $3 per GB-month for in-memory serving):

At 100 million documents ColBERTv2 costs about $300 a month more than a single-vector index and about $4,850 a month less than uncompressed ColBERT. Put that next to the cost of one engineer spending a week tuning chunk sizes to work around dilution, and the comparison stops being close.

Throughput, which is not the same question as latency

Latency is what one user waits. Throughput is what your fleet costs. They come apart badly here, and the difference decides architectures.

Take PLAID's 58 ms. Naively that is 1 / 0.058 = 17 queries per second on one GPU, which sounds ruinous. But 58 ms is single-stream latency, and most of it is spent waiting rather than computing: the query encoder is a tiny 32-token batch, and the centroid matmul is memory-bound. Batch eight queries together and almost all of that waiting is shared. Realistic sustained throughput lands nearer 100–150 QPS per accelerator, with latency rising to perhaps 80 ms.

Now the same arithmetic for the cross-encoder. 10,700 ms per query, batched perhaps 4× more efficiently, call it 2,700 ms of GPU time per query:

A hundredfold difference in serving cost for two systems that score within 0.05 MRR of each other. And BM25, for completeness: roughly 20 ms of one CPU core, so a 16-core machine sustains around 800 QPS and a million queries costs cents.

Two lessons hide in that table. The first is that latency and cost rank the systems in the same order but on wildly different scales — a 4× latency gap is a 100× cost gap. The second is that ColBERTv2 is the only row where a GPU is required and the cost is still small enough that most products would not notice it. That is a narrow and valuable position.

Which one should you build?

Notice that last row, because it is the most common production answer and it dissolves the framing of this whole chapter. These are not competitors. ColBERTv2 as a re-ranker over 1,000 candidates costs 0.6 GFLOPs and about 20 ms, gives you most of a cross-encoder's quality, and needs no index of its own if you fetch and encode on the fly. Late interaction is a stage, and you can put it wherever the budget allows.

Hybrid retrieval, and the fusion arithmetic

One more pattern, because it is nearly free and almost always helps: run BM25 and a neural retriever in parallel and fuse the two ranked lists. The standard method is Reciprocal Rank Fusion, which ignores the scores entirely (they are not comparable) and uses only the ranks:

Take a document ranked 3rd by BM25 and 15th by ColBERT:

against a document ranked 1st by BM25 and nowhere in ColBERT's top list:

The second document wins on one system and loses overall. That is the whole design: the constant k = 60 flattens the top of each list so a single system's confident first place cannot outvote broad agreement, which makes the fusion robust to one system being catastrophically wrong on a query. It works because BM25 and neural retrievers fail on different queries — BM25 on paraphrase, neural on rare entities — so their errors are close to uncorrelated.

Chapter 8: SPLADE — The Inverted Index Strikes Back

Chapter 0 pointed out, half as a joke, that BM25 already has the property late interaction is chasing: it stores evidence per term, it never pools, and a query addresses exactly the terms it cares about. This chapter takes that observation seriously, because a whole research line did.

First, respect the data structure

An inverted index maps each term to a posting list of the documents containing it, with a weight per posting. Scoring a query means walking a few posting lists and accumulating. It is worth listing what forty years of engineering bought that structure, because "just use vectors" quietly discards all of it.

Against that, BM25 has exactly one weakness: vocabulary mismatch. It matches strings. A query for "how deep" cannot match a passage saying "bathymetric depth", and a passage about "automobiles" is invisible to a query about "cars".

The mechanism, from BERT's own output head

BERT was pretrained with a masked language modelling head: a small network that maps each position's hidden state to a score for every one of the 30,522 wordpieces in the vocabulary. SPLADE reuses it exactly as-is.

where transform is the head's dense layer with GELU and LayerNorm, E is BERT's (tied) input embedding matrix, and b is the output bias. For an input of n positions this gives an (n, 30522) matrix of scores — every position's opinion about every vocabulary word.

Now collapse the position axis into a single sparse vector:

That is the whole representation. One number per vocabulary entry, most of them exactly zero.

Working it by hand

Take the passage "the mariana trench is deep" and look at what two of its positions vote for. Suppose the MLM head produces these raw scores (a handful of the 30,522 columns):

Apply log(1 + ReLU(·)) to each and add down the columns:

Two things to see. First, "ocean" has weight 1.3838 and the word "ocean" is not in the passage. The document will be indexed under "ocean" and will be retrievable by a query containing it. This is learned document expansion, produced by a head that was trained for something else entirely.

Second, "cooking" is exactly zero — not small, zero. ReLU produces true zeros, so the vector is structurally sparse and the term simply has no posting. That distinction matters enormously: a dense vector with small values still costs 4 bytes per dimension. A sparse vector with a structural zero costs nothing at all.

Why log(1 + ReLU(x)) and not something simpler

The two functions are doing two separate jobs and it is worth pulling them apart.

ReLU creates the sparsity. Any term the model thinks does not belong gets a negative score and lands on exactly zero. Without it you would have a dense 30,522-dimensional vector, which is far worse than a 768-dimensional one.

The logarithm creates saturation, and this is where SPLADE quietly rediscovers something BM25 knew in 1994. Consider a term appearing many times. BM25's term-frequency component is

Evaluate it at three frequencies:

Twenty occurrences are worth 2.08 times one occurrence, not twenty times. Now the log:

Twenty occurrences are worth 4.4 times one. Different constants, same shape: strongly concave, sharply rewarding the first occurrence, flattening after. Both are answers to the same problem — repetition is weak evidence of extra relevance and strong evidence of a keyword-stuffed document. SPLADE did not copy BM25's formula; it arrived at the same functional form because the underlying statistics of language have not changed.

Making it sparse enough to be fast

Nothing so far forces sparsity beyond what ReLU happens to produce, and a model with no pressure will happily light up thousands of terms. SPLADE adds an explicit regulariser whose form is chosen to approximate retrieval cost rather than to be mathematically tidy:

Read the square. The cost of a term during retrieval is roughly proportional to the probability that it appears in the query times the probability it appears in a document — a product, hence a square when both come from the same distribution. So this penalty charges quadratically for terms that are common in many documents, which is exactly where the long posting lists come from. An L1 penalty would charge linearly and would prefer to shave many rare terms rather than one very common one; the FLOPS penalty gets the priority right.

Two coefficients are used, λ_q for queries and λ_d for documents, with the query one larger because the number of query terms multiplies everything downstream. Typical outcomes: tens of non-zero terms in a query, a few hundred in a document, out of 30,522.

Scoring, and why it fits Lucene

A sparse dot product. Which is precisely what an inverted index computes — walk the posting lists for the query's non-zero terms, accumulate the products. The only change from a BM25 deployment is that the weight stored in each posting comes from a neural network instead of from a term-frequency formula. WAND still works. Compression still works. Sharding still works. The CPU still works.

Scoring a query against a document, by hand

Encode the query "how deep is the mariana trench" the same way and you get a sparse vector of its own — also expanded. Suppose it comes out as:

Look at the "ocean" row. That term appears in neither the query text nor the document text. Both sides expanded to it independently, and it contributes 0.84 — nearly 8% of the total score — through a posting list neither text would have entered under BM25. Expansion-to-expansion matching is where a large share of SPLADE's gain over BM25 comes from, and it is completely invisible if you only look at the surface strings.

Now score the same pair with BM25. The document text is "Challenger Deep plunges 10935 metres"; the query's content terms are "deep", "mariana", "trench". Exactly one matches. Two thirds of the query's evidence contributes nothing, and the passage that contains the answer is scored on a single term.

The efficiency problem expansion creates

Every one of those expansion terms is a posting, and postings are what an inverted index walks. Count them.

Three and a half times the postings is survivable. The problem is which postings. Expansion does not distribute uniformly across the vocabulary — models expand toward common, generic terms, because those are the ones the MLM head finds plausible everywhere. So the posting lists that grow are precisely the ones that were already longest, and query latency is dominated by the longest list you must traverse.

This is what the FLOPS regulariser's square is defending against, and it is why SPLADE's practical story is a whole efficiency literature: static pruning of the fattest lists, impact quantization so postings compress, and guided traversal that uses a BM25 index to bound the search. Left untuned, a learned sparse retriever can be an order of magnitude slower than the BM25 it was meant to replace, while running on the identical data structure.

ColBERT and SPLADE, side by side

The sharpest row is "keeps positional information". SPLADE aggregates over positions, so the passage's "deep" from "Challenger Deep" and a different passage's "deep" from "deep learning" both become a weight on the same vocabulary entry. Context is not lost entirely — the two passages will expand to different neighbouring terms, which distinguishes them — but the representation is fundamentally a bag of learned words. ColBERT keeps every position separate and pays for it in bytes.

Where each one still hurts

Chapter 9: Why Late Interaction Travels

Every number in this lesson so far came from MS MARCO. That is the dataset the models were trained on, and reporting quality on your training distribution is the weakest possible evidence about a retriever, because the entire promise of a retriever is that you point it at your corpus with your queries.

In 2021, BEIR (Thakur et al.) made this measurable: eighteen retrieval datasets across nine task types — fact checking, biomedical search, question answering, argument retrieval, duplicate detection, entity retrieval, citation prediction — all evaluated strictly zero-shot. Train on MS MARCO, evaluate everywhere else, report nDCG@10.

The result that reset the field

Three dense single-vector models, each of which beats BM25 by 12 to 16 MRR points on MS MARCO, lose to it on average across eighteen other datasets. A scoring function from the 1990s with no learned parameters beat the neural retrievers on the task the neural retrievers were sold for.

ColBERT, trained on exactly the same data with exactly the same encoder, does not lose. That is the observation this chapter has to explain.

Mechanism 1 — the summary was written for the wrong reader

Return to Chapter 0's bargain. A single-vector model must compress a passage into 768 numbers at index time. Compression is only possible because some information is discarded, and which information gets discarded is decided by the training objective.

Train on MS MARCO and the objective is: be discriminative for short, factoid, web-search queries typed by people using Bing. The encoder learns, correctly, that for that query distribution the important thing about a passage is its topical gist and its named entities, and that fine distinctions between claim types, methodological details, or numerical values rarely decide a MS MARCO ranking. It compresses along those axes.

Now point it at SciFact, where the query is a scientific claim and the task is to find the abstract that supports or refutes it. Or FiQA, where the query is a financial question and relevance turns on the exact instrument being discussed. The dimensions the encoder learned to discard are precisely the ones that now carry the signal.

Mechanism 2 — late interaction degrades into term matching

The second mechanism is more specific, and it is a lovely piece of reasoning about what happens to an embedding model outside its training vocabulary.

Suppose a BEIR query contains a token the model has essentially never trained on — a drug name, a protein, a ticker symbol, an obscure API. What does BERT produce at that position? The contextual embedding is built from the input wordpiece embedding plus position plus whatever the surrounding context contributes. For a token the model has no learned semantics for, the input embedding term dominates and the output is largely a function of the surface form.

Now consider a document containing the same rare token. Its contextual embedding is built the same way, from the same input embedding, in a broadly similar context. The two vectors will be close — not because the model understands the term, but because it is the same wordpiece running through the same network.

MaxSim gives that query token its own row, and its row max finds the document token with the same surface form, scoring near 1. The rare term contributes a full unit of evidence to the sum. Late interaction degrades gracefully into exact term matching exactly where semantics fail. It inherits BM25's robustness for free, without a single line of lexical code.

A pooled vector cannot do this. The rare token is one of n contributions to an average, so it moves the summary vector by roughly 1/n — about 1.4% for a 73-token passage — and that displacement is then compared against the query's own averaged displacement. The signal survives, technically, at a strength of about one part in seventy against everything else in the document.

Mechanism 3 — addressable capacity

The simplest argument, saved for last because it is the least interesting on its own. A 73-token passage at 128 dimensions is 9,344 numbers against a single vector's 768: about 12× the capacity.

But capacity alone explains nothing — you could give DPR 9,344 dimensions and it would not reach ColBERT's BEIR score. What matters is that the capacity is addressable: organised so that a query token can read the part it needs without being averaged against the rest. A 9,344-dimensional pooled vector is still one summary. Seventy-three 128-dimensional vectors are seventy-three separately retrievable pieces of evidence. Structure beats size.

Dataset by dataset, including where it loses

Look at the DPR column all the way down. It loses to BM25 on every single row, often catastrophically — 0.112 against 0.236 on FiQA, 0.248 against 0.789 on Quora. That is not a model that generalises weakly; that is a model whose representation is specific to the distribution it was fit on.

Where late interaction loses, and exactly why

Two rows deserve mechanistic explanations rather than shrugs, because a lesson that only explains the wins is advertising.

ArguAna (0.233 vs BM25's 0.315). The task: given an argument, retrieve its best counter-argument. Two structural problems. First, ArguAna's queries are entire paragraphs, and ColBERT truncates queries at 32 wordpieces — most of the query is thrown away before scoring. That is not a subtle modelling issue, it is a hard architectural limit being hit head-on. Second, MaxSim rewards similarity, and a counter-argument is topically similar but stance-opposite; nothing in the objective distinguishes agreement from disagreement.

Touché-2020 (0.202 vs BM25's 0.367). Long argumentative documents, truncated at ColBERT's 180-token document limit, on a task where relevance means argument quality rather than topical match. Also, Touché is known to have shallow and idiosyncratic judgements that happen to favour long documents — which BM25's length normalisation, tuned over decades on exactly this kind of collection, handles well.

Both failures share a root: a fixed window. 32 query positions and 180 document positions were chosen for MS MARCO's short queries and short passages. Out of domain, those constants stop being generous defaults and start being the model.

The principle, stated so it outlives the paper

Strip away retrieval and the finding is about system design in general.

That asymmetry is the whole lesson. Late interaction wins the generalisation argument not because MaxSim is clever — it is three lines of tensor code — but because it declines to commit. The engineering work of ColBERTv2 and PLAID is then entirely about making the cost of not committing affordable, and it turns out that cost is compressible while lost information is not.

Where the idea went

The ColPali row is the one that shows the idea was never about text. MaxSim needs two bags of vectors and nothing else. Give it image patches instead of wordpieces and it retrieves pages by their visual content, because "keep one vector per piece and let the query choose" was never a statement about language.

Connections

Where to go from here on this site:

The cheat sheet

The four equations, in order.

References

1. Khattab, O. & Zaharia, M. "ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT." SIGIR 2020. arXiv:2004.12832
2. Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C. & Zaharia, M. "ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction." NAACL 2022. arXiv:2112.01488
3. Santhanam, K., Khattab, O., Potts, C. & Zaharia, M. "PLAID: An Efficient Engine for Late Interaction Retrieval." CIKM 2022. arXiv:2205.09707
4. Formal, T., Piwowarski, B. & Clinchant, S. "SPLADE: Sparse Lexical and Expansion Model for First Stage Ranking." SIGIR 2021. arXiv:2107.05720
5. Formal, T., Lassance, C., Piwowarski, B. & Clinchant, S. "SPLADE v2: Sparse Lexical and Expansion Model for Information Retrieval." 2021. arXiv:2109.10086
6. Formal, T. et al. "From Distillation to Hard Negative Sampling: Making Sparse Neural IR Models More Effective." SIGIR 2022. arXiv:2205.04733
7. Karpukhin, V. et al. "Dense Passage Retrieval for Open-Domain Question Answering." EMNLP 2020. arXiv:2004.04906
8. Thakur, N., Reimers, N., Rücklé, A., Srivastava, A. & Gurevych, I. "BEIR: A Heterogeneous Benchmark for Zero-shot Evaluation of Information Retrieval Models." NeurIPS Datasets 2021. arXiv:2104.08663
9. Nogueira, R. & Cho, K. "Passage Re-ranking with BERT." 2019. arXiv:1901.04085
10. Qu, Y. et al. "RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering." NAACL 2021. arXiv:2010.08191
11. Xiong, L. et al. "Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval" (ANCE). ICLR 2021. arXiv:2007.00808
12. Hofstätter, S. et al. "Efficiently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling" (TAS-B). SIGIR 2021. arXiv:2104.06967
13. Faysse, M. et al. "ColPali: Efficient Document Retrieval with Vision Language Models." 2024. arXiv:2407.01449
14. Devlin, J., Chang, M.-W., Lee, K. & Toutanova, K. "BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding." NAACL 2019. arXiv:1810.04805
15. Nguyen, T. et al. "MS MARCO: A Human Generated MAchine Reading COmprehension Dataset." 2016. arXiv:1611.09268
16. Robertson, S. & Zaragoza, H. "The Probabilistic Relevance Framework: BM25 and Beyond." Foundations and Trends in Information Retrieval, 2009.
17. Cormack, G. V., Clarke, C. L. A. & Buettcher, S. "Reciprocal Rank Fusion Outperforms Condorcet and Individual Rank Learning Methods." SIGIR 2009.