Cranfield query 185 asks for experimental studies on panel flutter. A bi-encoder squeezes it into one vector, and Dense Passage Retrieval found the result putting a review of panel flutter, abstract 658, above the experimental study that is the best answer, abstract 856: the word experimental got only a share of one direction. Suppose instead the query keeps a vector for each of its words, and each word looks for its own best match in the abstract. Then experimental finds experimental in abstract 856 with a cosine of 0.914, and in abstract 658, whose title is a review, its best match scores 0.707. What does such a model gain, what does it cost, and where does it sit between a bi-encoder and a cross-encoder?
Late interaction is the design in which a query and a document are encoded separately, each into one vector per token, and are compared only at the end, by a cheap function of the two sets of vectors. The function used by ColBERT (Khattab and Zaharia, 2020) sums, over the query's vectors, each one's largest similarity with any of the document's vectors; this is called MaxSim. Because the document's vectors do not depend on the query, they are computed once at indexing time, as a bi-encoder's are. Because the comparison keeps each query token separate, it is finer than a single dot product.
Here is the route. First we place late interaction between the bi-encoder and the cross-encoder of Sentence and Passage Encoders. Then we set out ColBERT's encoders and score, and prove four properties of MaxSim. Then we work query 185 against three abstracts token by token, rank all of Cranfield with the pretrained ColBERTv2, and vary the scoring rule at query time. Next comes the cost: the arithmetic of the score, the size of the index, and ColBERTv2's residual compression, which we reimplement and measure. The article assumes Sentence and Passage Encoders and Dense Passage Retrieval. The numbers are computed by tools/experiments/neural-ranking/late-interaction-and-colbert.py.
Between one vector and full attention
Sentence and Passage Encoders sets out the two ways of scoring with a transformer. A cross-encoder reads the query and the document as one input, so every query token attends to every document token in every block, and nothing can be computed before the query arrives: one pass through the network per pair. A bi-encoder reads each text alone and pools its token vectors into one, so documents are encoded in advance and a query costs one pass plus a dot product per document. Cross-Encoder Re-ranking measures the first, and Limits of Single-Vector Retrieval the price of the second's pooling.
Late interaction takes the bi-encoder's separation and drops its pooling. Both texts are still encoded alone, so document vectors are still computed in advance. But the token vectors are kept, all of them, and the query and document meet in a function that looks at every pair of tokens without any attention or learned parameters. Lin (2021) puts the bi-encoder and the cross-encoder at the two ends of one design, distinguished by the comparison function: a dot product of two finished vectors at one end, the whole transformer at the other. Late interaction lies between them: its comparison sees every token, but only after encoding, and it is cheap.
ColBERT
The encoders
Khattab and Zaharia (2020, §3.2) share one BERT network between queries and documents and mark which is which with a special token placed after BERT's [CLS]: [Q] for a query and [D] for a document. (In the released code these are the vocabulary's unused entries [unused0] and [unused1].)
- Query. The query's word pieces are prefixed with
[CLS] [Q]and padded with BERT's[MASK]token to a fixed length $N_q = 32$ (truncated if longer). The paper calls this query augmentation and describes it as "a soft, differentiable mechanism" for learning "to expand queries with new terms or to re-weigh existing terms": the output vectors at the[MASK]positions are kept and take part in the score. - Document. The word pieces are prefixed with
[CLS] [D]; no masks are added. After encoding, the vectors at punctuation tokens are dropped, to reduce the number of vectors stored. - Both. BERT's output at each position passes through a linear layer with no activation that reduces it to $m = 128$ dimensions, and each vector is then scaled to unit length, so that a dot product is a cosine.
In their notation (§3.2, equations 1 and 2), with # for the mask tokens,
$$E_q := \mathrm{Normalize}(\mathrm{CNN}(\mathrm{BERT}(\text{"[Q]} q_0 q_1 \dots q_l \#\# \dots \#\text{"}))),$$ $$E_d := \mathrm{Filter}(\mathrm{Normalize}(\mathrm{CNN}(\mathrm{BERT}(\text{"[D]} d_0 d_1 \dots d_n\text{"})))),$$
where the equations write "CNN" for the step the text describes as the linear layer. The released ColBERTv2 checkpoint stores its settings with it: query length 32, document length 180 positions, dimension 128, punctuation masked, and the [MASK] positions excluded from attention (attend_to_mask_tokens false), so that no real token attends to them while they attend to the real tokens.
The score
Write the query's vectors as $\vec q_1, \dots, \vec q_{N_q}$ and the document's as $\vec d_1, \dots, \vec d_{L_d}$, all unit vectors in $\mathbb{R}^m$. The late-interaction score (their equation 3) is
$$S(q, d) = \sum_{i=1}^{N_q} \max_{j = 1, \dots, L_d} \vec q_i \cdot \vec d_j .$$
Each query vector finds the document vector most like it, and the best similarities are added. The paper's description is that the mechanism "softly searches for each query term ... against the document's embeddings, quantifying the strength of the 'match' via the largest similarity score". The comparison has no trainable parameters; everything learned is in the encoders.
ColBERT was trained on MS MARCO triples (a query, a relevant passage, a BM25-retrieved negative) with a softmax cross-entropy over the two scores (§3.3), with BERT-base, learning rate $3 \times 10^{-6}$ and batches of 32 (§4.1.2). ColBERTv2 (Santhanam et al., 2022, §3.2) kept the architecture and changed the supervision: negatives mined from an index built with the model itself, 64 passages per query scored by a 22-million-parameter MiniLM cross-encoder, and a KL-divergence loss that trains ColBERT's scores to match the cross-encoder's distribution, plus in-batch negatives. This is the distillation of Hard Negatives and Distillation, with a different loss.
What can be proved about MaxSim
Four properties follow from the definition. They hold for any unit vectors, trained or not.
Proposition 1 (one vector each is a dot product). If $N_q = L_d = 1$, then $S(q, d) = \vec q_1 \cdot \vec d_1$.
Proof. With one term in the sum and one in the maximum, the score is the single dot product. $\square$
So a bi-encoder is the special case of late interaction with one vector per text, and late interaction generalizes it by keeping more.
Proposition 2 (averaging collapses to one vector). Replace the maximum by the mean over the document's vectors. The resulting score equals $N_q\, \bar{q} \cdot \bar{d}$, where $\bar q$ and $\bar d$ are the means of the query's and the document's vectors; it therefore ranks documents exactly as the dot product of mean-pooled vectors does. And it never exceeds MaxSim:
$$\sum_{i=1}^{N_q} \frac{1}{L_d} \sum_{j=1}^{L_d} \vec q_i \cdot \vec d_j \;=\; N_q\, \bar q \cdot \bar d \;\le\; S(q, d).$$
Proof. For the equality, the dot product is linear in each argument: $\sum_i \frac{1}{L_d} \sum_j \vec q_i \cdot \vec d_j = \big(\sum_i \vec q_i\big) \cdot \big(\frac{1}{L_d} \sum_j \vec d_j\big) = N_q \bar q \cdot \bar d$. For a fixed query $N_q \bar q$ is a fixed vector, so the ranking is that of $\bar q \cdot \bar d$. For the inequality, a mean of numbers never exceeds their maximum, so each term $\frac{1}{L_d}\sum_j \vec q_i \cdot \vec d_j \le \max_j \vec q_i \cdot \vec d_j$, and summing over $i$ keeps the inequality. $\square$
The paper's ablation [B] trained a model with average similarity in place of the maximum and found it clearly worse (their Figure 5, a figure without tabulated values). Proposition 2 says what that model was: a bi-encoder with mean pooling (of unnormalized vectors), whatever its training. The maximum is what makes the design more than one vector.
Proposition 3 (bounds and monotonicity). $-N_q \le S(q, d) \le N_q$. Adding vectors to a document never lowers its score, and removing vectors never raises it.
Proof. Each term is a cosine of unit vectors, between $-1$ and $1$, and there are $N_q$ terms. If the document's set of vectors grows, each maximum is taken over a larger set and cannot fall, so neither can the sum; removing vectors is the same argument reversed. $\square$
Two consequences matter in practice. A longer document has more chances to match each query vector, and nothing in the score corrects for length, unlike BM25's length normalization. And a search that looks at only some of a document's vectors gets a score that is too low, never too high, which is the next proposition.
Proposition 4 (partial search is a lower bound). Let $J_i \subseteq \{1, \dots, L_d\}$ be any nonempty set of the document's vectors examined for query vector $i$, and $\tilde S(q, d) = \sum_i \max_{j \in J_i} \vec q_i \cdot \vec d_j$. Then $\tilde S(q, d) \le S(q, d)$, with equality exactly when, for every $i$, $J_i$ contains a vector at which the full maximum is reached.
Proof. For each $i$, the maximum over the subset $J_i$ is at most the maximum over all $j$, with equality exactly when the subset contains a maximizer. Summing over $i$ gives the inequality, and the sum of nonnegative differences is zero exactly when every difference is zero. $\square$
This is what makes late interaction usable as a first stage. ColBERT's end-to-end retrieval (§3.6) searches, for each of the 32 query vectors, a vector index over all document vectors of the collection, and maps the hits back to their documents; the documents found this way are then scored exactly. ColBERTv2's candidate generation (§3.5) does the same with its centroids: for each query vector it scans the document vectors near its nearest centroids and max-reduces the similarities per document, which, in the paper's words, "computes a lower-bound on the true MaxSim". Proposition 4 is that lower bound, and it says when the bound is exact. (ColBERTv2 computes it on compressed vectors, so it bounds MaxSim over the compressed vectors; Proposition 5 below bounds how far that is from the score over the originals.)
Query 185, token by token
The pinned model is colbert-ir/colbertv2.0 at revision c1e84128e85ef755c096a95bdb06b47793b13acf, the checkpoint released with the ColBERTv2 paper (MIT licence). Its encoder is our transcription of the reference implementation (the ColBERT repository at commit cc4f3dc), with the checkpoint's own settings; there is no ColBERT library in the environment to compare against, so the transcription's correctness rests on reading the code and on the results below.
Query 185 becomes 32 vectors: [CLS], [Q], experimental, studies, on, panel, flutter, the full stop, [SEP], and 23 [MASK] positions. Against abstract 856 (some experimental studies of panel flutter at mach 1.3, 159 vectors), each query vector's best match is:
| Query vector | Best match in abstract 856 | Cosine |
|---|---|---|
[CLS] |
[CLS] |
0.706 |
[Q] |
experimental | 0.902 |
| experimental | experimental | 0.914 |
| studies | studies | 0.910 |
| on | the | 0.697 |
| panel | panel | 0.904 |
| flutter | flutter | 0.902 |
| full stop | flutter | 0.883 |
[SEP] |
[CLS] |
0.698 |
23 [MASK] vectors |
flutter 9, panel 6, studies 4, experimental 4 | 20.369 in all |
The nine vectors of real tokens contribute 7.516 and the 23 mask vectors 20.369, a total of $S = 27.885$. Nearly three quarters of the score comes from the augmentation, and the mask vectors spread themselves over the query's content words: each acts as an extra, softer copy of one of them.
Against abstract 658, the review of panel flutter (164 vectors), panel and flutter match as well as before (0.910 and 0.881), but experimental finds only 0.707 and studies finds review at 0.342. The total is 23.203. Against abstract 864, a status report of 58 vectors that is the dense retriever's second result, experimental and studies find nothing better than results (0.226 and 0.390), and the total is 21.037. The ordering 856, 658, 864 is the one the query asks for, and it comes mostly from the two words a single vector diluted. Of the 4.682 by which abstract 856 beats 658, 4.042 comes from the query vectors whose best match in 856 is experimental or studies: the two words themselves (0.775), the [Q] marker (0.228) and the mask vectors that copy them (3.039). Over all 1,400 abstracts, ColBERTv2's top ten for query 185 are 856, 857, 1008, 390, 766, 15, 858, 627, 658 and 948, with an nDCG@10 of 0.732, against 0.807 for BM25 and 0.290 for the dense retriever.
ColBERTv2 on Cranfield
Each of the 1,400 abstracts was encoded once, and every query was scored against all of them by MaxSim, with no approximation. The baselines are those of Dense Passage Retrieval: BM25 with the course's analyzer and the unit's bi-encoder, with nDCG@10 using gain $5 - \text{grade}$ and recall counting any graded abstract as relevant.
| Ranker | nDCG@10 | Recall@10 | Recall@100 | Recall@1000 |
|---|---|---|---|---|
| BM25 | 0.368 | 0.397 | 0.737 | 0.952 |
| Dense (bi-encoder, one vector) | 0.382 | 0.416 | 0.772 | 0.989 |
| ColBERTv2 (exhaustive MaxSim) | 0.367 | 0.394 | 0.749 | 0.977 |
On this collection late interaction is not ahead of either baseline. Against BM25 the difference in nDCG@10 is $-0.001$ ($t = -0.11$, $p = 0.91$; better on 99 queries, worse on 91), and in recall@100 $+0.012$ ($p = 0.28$). Against the dense retriever it is $-0.015$ ($p = 0.26$) and in recall@100 $-0.024$ ($p = 0.065$). Neither difference can be told from chance with 225 queries.
Example (a stronger model is not stronger everywhere). It is natural to expect the more expressive model to win, and on its training data it did: ColBERTv2's paper reports an MRR@10 of 39.7 on MS MARCO's development queries, above every other system in its Table 4. Cranfield is far from MS MARCO, and the measurements of Limits of Single-Vector Retrieval on BEIR showed that out of domain, models' rankings shuffle; there, the original ColBERT was above BM25 on 9 of 18 datasets. One cause on Cranfield can be measured. The checkpoint reads at most 180 positions of a document, which leaves 177 word pieces once [CLS], [D] and [SEP] are placed, and 756 of the 1,400 abstracts are longer: more than half are cut, and late interaction never sees their ends. Read up to 512 positions, which leaves only 23 abstracts cut, the index holds 270,397 vectors in place of 198,189, and nDCG@10 rises to 0.380 (+0.013, $p = 0.035$) while recall@100 barely moves, from 0.749 to 0.752 ($p = 0.62$). The cut explains part of the gap at the top of the list, and even with nearly whole abstracts late interaction does not pull ahead of the dense retriever's 0.382 here. (The configuration stored with the checkpoint, which names its training run, cuts documents at 180 positions; reading further is something it was not trained for, and it helped anyway.)
Changing the scoring at query time
The trained model can be scored differently without retraining. These variants test which parts of the design carry the result on this collection; they are not the paper's ablations, which retrained a model for each.
| Variant (same trained model) | nDCG@10 | Difference from full | $p$ |
|---|---|---|---|
| Full MaxSim, 32 query vectors | 0.367 | ||
The [MASK] vectors left out of the sum |
0.348 | −0.019 | 0.0003 |
| Mean in place of the maximum (Proposition 2) | 0.219 | −0.148 | < 0.0001 |
Cranfield's queries are long for a 32-position query: the median query leaves room for only 9 [MASK] positions (query 185, with 23, is one of the shortest), 43 queries have none, and 38 are longer than the 29 word pieces that fit and are cut. Leaving out the mask vectors costs 0.019. Encoding the queries with no [MASK] padding at all gives exactly the same vectors for the real tokens, because the masks are excluded from attention; the script checks that the two variants give identical vectors to within the stored precision and the same top ten for every query. So on this collection the augmentation helps, as the paper's ablation [C] found on MS MARCO, and it helps only by adding vectors to the sum. Replacing the maximum by the mean, which by Proposition 2 turns the model into a mean-pooled single vector, loses 0.148 and falls far below the dense retriever: this model's token vectors were trained to be matched individually, not averaged.
Late interaction on vectors not trained for it. The opposite experiment takes the unit's bi-encoder, all-MiniLM-L6-v2, which was trained to be mean-pooled, and scores Cranfield by MaxSim over its token vectors (each scaled to unit length). It scores 0.383 in nDCG@10, against 0.382 for the same network's pooled vector ($p = 0.89$). Keeping the tokens of a network trained for one vector neither helped nor hurt here, which is consistent with the papers' view that the gain comes from training the token vectors for MaxSim; this one comparison does not test that view.
What it costs
Arithmetic
Scoring one query against one document takes $N_q \times L_d$ dot products of $m$ numbers, that is $N_q L_d m$ multiply-adds. On Cranfield the abstracts keep 141.6 vectors on average, so one pair costs $32 \times 141.6 \times 128 \approx 580{,}000$ multiply-adds, and one query against the whole collection
$$32 \times 198{,}189 \times 128 = 811{,}782{,}144$$
multiply-adds, where 198,189 is the total number of stored vectors. The bi-encoder needs $1{,}400 \times 384 = 537{,}600$, about 1,510 times fewer. Scoring all 225 queries exhaustively took seconds on the laptop that ran the script (the script prints the timing; it varies with the machine's load and is not asserted). A cross-encoder costs far more: Khattab and Zaharia (Table 1) estimate 97 trillion floating-point operations per query to re-rank 1,000 MS MARCO passages with BERT-base, against 7 billion for ColBERT, about 13,900 times fewer, and report 61 milliseconds of re-ranking latency on a GPU against 10,700.
Storage
The price is paid in the index. Each document stores a vector per token. On Cranfield, at 16 bits per number,
$$198{,}189 \times 128 \times 2 = 50{,}736{,}384 \text{ bytes},$$
50.7 megabytes, against 2,150,400 bytes for the bi-encoder's one 384-number vector per abstract at 32 bits: 23.6 times as much. For MS MARCO's 8.8 million passages, the paper's Table 4 gives 286 GiB at 4 bytes per number and 154 GiB at 2 bytes, and as little as 27 GiB with 24 dimensions at 2 bytes, at an MRR@10 of 33.9 against 34.9. Lin and Ma (2021) set the 154 GiB beside 26 GB for a dense single-vector index and 1.3 GB for a learned sparse one (Learned Sparse Retrieval).
Residual compression
ColBERTv2 (§3.3) reduces the vectors to a few bytes each. Here is the idea: token vectors of the same word in similar contexts lie close together, so each vector is stored as the index of its nearest centroid plus a coarse correction.
Choose centroids $\vec C_1, \dots, \vec C_K$ with k-means over the collection's vectors. Store each vector $\vec v$ as the index $t$ of its nearest centroid and its residual $\vec r = \vec v - \vec C_t$ quantized coordinate by coordinate to $b$ bits, that is to one of $2^b$ values. The reconstruction is $\tilde{\vec v} = \vec C_t + \tilde{\vec r}$. The paper counts $\log_2 K + b m$ bits per vector and in practice stores 4 bytes for the centroid index and 16 or 32 bytes for the residual at $b = 1$ or 2, so 20 or 36 bytes per vector against 256 bytes at 16 bits. The released code fixes what the paper leaves open. The number of centroids is $2^{\lfloor \log_2(16 \sqrt{n}) \rfloor}$ for $n$ vectors. The $2^b - 1$ cutoffs between quantization levels are the quantiles $1/2^b, \dots, (2^b - 1)/2^b$ of the residual values of a held-out 5% of the vectors, pooled over all coordinates, and each level is reconstructed as the quantile at the middle of its range. The code also adds three steps that the paper's formula does not show: after k-means it scales the centroids to unit length, it assigns each vector to the centroid of largest dot product (with unit centroids, the nearest by angle), and it scales each reconstruction $\vec C_t + \tilde{\vec r}$ back to unit length.
How far can compression move a score? The answer is a bound in terms of the reconstruction error.
Proposition 5. Let every document vector $\vec d_j$ be replaced by $\tilde{\vec d}_j$, and let $\tilde S$ be MaxSim over the replacements. Then
$$\lvert S(q, d) - \tilde S(q, d) \rvert \;\le\; \sum_{i=1}^{N_q} \max_j \lvert \vec q_i \cdot (\vec d_j - \tilde{\vec d}_j) \rvert \;\le\; N_q \max_j \lvert \vec d_j - \tilde{\vec d}_j \rvert .$$
Proof. First a fact about maxima: for numbers $a_1, \dots, a_L$ and $b_1, \dots, b_L$, $\lvert \max_j a_j - \max_j b_j \rvert \le \max_j \lvert a_j - b_j \rvert$. To see it, let $a_k$ be the largest $a$; then $\max_j a_j - \max_j b_j \le a_k - b_k \le \max_j \lvert a_j - b_j \rvert$, and exchanging the roles of $a$ and $b$ bounds the difference the other way. Apply this with $a_j = \vec q_i \cdot \vec d_j$ and $b_j = \vec q_i \cdot \tilde{\vec d}_j$ for each $i$, and sum over $i$ with the triangle inequality: that is the first inequality. For the second, the Cauchy-Schwarz inequality gives $\lvert \vec q_i \cdot (\vec d_j - \tilde{\vec d}_j) \rvert \le \lvert \vec q_i \rvert \lvert \vec d_j - \tilde{\vec d}_j \rvert = \lvert \vec d_j - \tilde{\vec d}_j \rvert$, since $\vec q_i$ is a unit vector. $\square$
The script reimplements the scheme on Cranfield's 198,189 vectors: $K = 2^{\lfloor \log_2(16\sqrt{198{,}189}) \rfloor} = 4{,}096$ centroids. To keep each run to under a minute, k-means is fitted on a random sample of 65,536 of the vectors for 10 iterations, where the reference indexer, for a collection this small, would use every vector except the held-out 5%, and the checkpoint's stored setting is 20 iterations. The rest follows the code: unit centroids, assignment by largest dot product, quantized residuals and renormalized reconstructions. The held-out 5% for the cutoffs is drawn from the vectors outside the sample. The random parts (sample, starting centroids, held-out set) are seeded, with 30 seeds, 0 to 29; the table gives medians with interquartile ranges in brackets. The queries are not compressed.
| Stored vector | Bytes per vector | nDCG@10 | Recall@100 | Mean distance from the original | Queries with the same top ten |
|---|---|---|---|---|---|
| 16-bit numbers, uncompressed | 256 | 0.367 | 0.749 | 0 | 225 |
| Centroid index only | 4 | 0.343 [0.340, 0.345] | 0.754 [0.752, 0.757] | 0.448 | 0 [0, 0] |
| Centroid and 1-bit residual | 20 | 0.363 [0.361, 0.364] | 0.755 [0.753, 0.758] | 0.296 | 1 [0, 1] |
| Centroid and 2-bit residual | 36 | 0.368 [0.366, 0.369] | 0.754 [0.752, 0.755] | 0.192 | 8.5 [7, 10] |
On this collection compression costs almost nothing in the measures, and the residual is what makes it cheap. The centroid alone, 4 bytes in place of 256, moves the unit-length vectors by 0.448 on average and costs 0.024 in nDCG@10. One bit per coordinate recovers most of that and two bits all of it: at 36 bytes per vector, a seventh of the 16-bit size, nDCG@10 is 0.368 against 0.367 uncompressed, and recall@100 is 0.754 (0.750 to 0.759 over the 30 seeds), slightly above the uncompressed 0.749 on every seed. ColBERTv2's paper reports the same pattern on MS MARCO (its Appendix B): a ColBERT model with an MRR@10 of 36.2 kept 36.2 at 2 bits and fell to 35.5 at 1 bit, and recall@50 went from 82.1 to 82.3 and 81.6.
The rankings themselves do move: at 2 bits, a median of only 8.5 of the 225 queries keep exactly the same top ten. Proposition 5 allows far more movement than occurs. The farthest any compressed vector lies from its original is 0.870 (median over seeds, at 2 bits), so the bound allows a 32-vector query's score to move by up to 27.8, about a whole score. Reaching it would need every query vector's best match to be among the worst-compressed vectors with every error pointing the same way. The scores actually move by much less, enough to swap close neighbors in many top tens and, on these measures, too little to change effectiveness. Why the scores move so much less than the bound was not measured across the collection; worked problem 5 takes one case apart. The script checks the bound for every abstract on 15 queries at each setting of seed 0.
What is proved here, what is cited, and what the experiment shows
Proved on this page. Propositions 1 to 5: that MaxSim with one vector a side is a dot product; that averaging in place of the maximum is exactly a mean-pooled single-vector score, and never exceeds MaxSim; the bounds and the monotonicity of the score in the document's vectors; that a search over part of the vectors gives a lower bound, exact when it contains each maximizer; and the bound on the effect of compressing the document vectors. The arithmetic of cost and storage.
Cited. ColBERT's architecture, training, settings, ablations, costs and MS MARCO results (Khattab and Zaharia, 2020); ColBERTv2's supervision, residual compression, centroid rule, candidate generation, index sizes and results (Santhanam et al., 2022), with the details of the released code; the conceptual frame (Lin, 2021); index sizes compared by Lin and Ma (2021).
Shown by the experiment, for one checkpoint on one small collection out of its training domain. ColBERTv2 with exhaustive MaxSim is indistinguishable from BM25 and from the unit's bi-encoder on Cranfield. On query 185 its per-token matching separates the experimental study from the review where the single vector did not. The [MASK] vectors add about 0.02 in nDCG@10; replacing the maximum with the mean loses 0.15. MaxSim over a bi-encoder's token vectors changes nothing. The index is 23.6 times the bi-encoder's at 16 bits, and residual compression, reimplemented as the released code does it, to 36 bytes per vector left nDCG@10 where it was and recall@100 slightly above while changing most queries' top ten.
Worked problems
These problems are posed on small exact cases and on Cranfield; the unit has no course assignments. The script recomputes each number.
Problem 1 (MaxSim by hand). A query has two unit vectors in the plane, $\vec q_1 = (1, 0)$ and $\vec q_2 = (0.6, 0.8)$. Document A has vectors $(0.8, 0.6)$ and $(0, 1)$; document B has the single vector $(0.96, 0.28)$. Compute both scores, and compare with the bi-encoder that mean-pools and normalizes each side.
Solution. For A: $\vec q_1$ matches $(0.8, 0.6)$ with 0.8 and $(0, 1)$ with 0, so its best is 0.8; $\vec q_2$ matches them with $0.48 + 0.48 = 0.96$ and 0.8, so its best is 0.96. $S(q, A) = 0.8 + 0.96 = 1.76$. For B: $\vec q_1 \cdot (0.96, 0.28) = 0.96$ and $\vec q_2 \cdot (0.96, 0.28) = 0.576 + 0.224 = 0.8$, so $S(q, B) = 1.76$. A tie. With mean pooling, $\bar q = (0.8, 0.4)$, of length $\sqrt{0.8} = 0.894$; A's mean is $(0.4, 0.8)$, of the same length; B's is itself. The cosines are $\cos(\bar q, \bar A) = (0.32 + 0.32)/0.8 = 0.8$ and $\cos(\bar q, B) = (0.768 + 0.112)/0.894 = 0.984$. The bi-encoder strongly prefers B, whose single vector lies between the query's two directions; MaxSim credits A for matching each query vector with a different one of its own.
Problem 2 (counting the work). A collection has 10,000 passages of 60 stored vectors each, $m = 128$, and queries of $N_q = 32$ vectors. How many multiply-adds does exhaustive MaxSim take per query, and how many does a bi-encoder of dimension 768 take? How many bytes does each index take at 2 bytes per number?
Solution. MaxSim: $32 \times 10{,}000 \times 60 \times 128 = 2{,}457{,}600{,}000$, about 2.5 billion. Bi-encoder: $10{,}000 \times 768 = 7{,}680{,}000$, which is 320 times fewer. Storage: $10{,}000 \times 60 \times 128 \times 2 = 153{,}600{,}000$ bytes for late interaction, $10{,}000 \times 768 \times 2 = 15{,}360{,}000$ for the bi-encoder, ten times less: the ratio is $60 \times 128 / 768 = 10$. The compute ratio is larger by the factor $N_q = 32$, since every query vector is compared, where the bi-encoder compares one.
Problem 3 (the average rule). For the query and documents of Problem 1, compute the average-similarity score $\sum_i \frac{1}{L_d}\sum_j \vec q_i \cdot \vec d_j$ for both documents and check Proposition 2.
Solution. For A, the four dot products are 0.8, 0, 0.96 and 0.8, and the score is $(0.8 + 0)/2 + (0.96 + 0.8)/2 = 0.4 + 0.88 = 1.28$. By Proposition 2 it equals $N_q \bar q \cdot \bar A = 2 \times (0.8 \times 0.4 + 0.4 \times 0.8) = 2 \times 0.64 = 1.28$. For B, with one vector, it is $0.96 + 0.8 = 1.76$, and $2 \times (0.8 \times 0.96 + 0.4 \times 0.28) = 2 \times 0.88 = 1.76$. Both are at most their MaxSim, 1.76, with equality for B, whose single vector makes mean and maximum the same.
Problem 4 (candidate generation). In Problem 1, suppose a vector index returns, for $\vec q_1$, only document A's vector $(0, 1)$, and for $\vec q_2$, only A's vector $(0.8, 0.6)$. What lower bound does Proposition 4 give for $S(q, A)$, and when would the bound have been exact?
Solution. $\tilde S = \vec q_1 \cdot (0, 1) + \vec q_2 \cdot (0.8, 0.6) = 0 + 0.96 = 0.96 \le 1.76$. The bound is exact only if each query vector's set contains its maximizer: $\vec q_1$'s best in A is $(0.8, 0.6)$, which was not returned for it, so the bound is short by 0.8. This is why the documents found by candidate generation are re-scored exactly before the final ranking.
Problem 5 (the compression bound). At 2 bits with seed 0, no compressed vector of abstract 856 lies farther than 0.391 from its original. Query 185 has 32 vectors. How far can the abstract's score for query 185 move, and how far did it move?
Solution. By Proposition 5, by at most $32 \times 0.391 \approx 12.5$. The score moved from 27.885 to 27.623, by 0.263, about a fiftieth of the bound. The measurement shows where the slack lies. Each term $\max_j \lvert \vec q_i \cdot (\vec d_j - \tilde{\vec d}_j) \rvert$ equals the largest error's length only if that error points along $\vec q_i$; here the errors make angles with the query vectors whose cosine averages 0.094 in absolute value, and the sum of the 32 terms, the middle expression of Proposition 5, is 3.30, not 12.5. Each of those terms also takes the worst error over all 159 of the abstract's vectors, while a best match moves only with the errors of the vectors that compete for it: the 32 best matches moved by 0.282 in all. Their signs barely cancel (29 of the 32 fell), so the net change is 0.263. The bound is a guarantee, not an estimate: compression cannot reverse the order of two abstracts unless their scores were within the sum of their two bounds.
What we have learned
Late interaction keeps a vector per token on both sides and compares them only at the end: each query vector takes its best match in the document, and the matches are summed. With one vector a side this is a bi-encoder; with the mean in place of the maximum it is a mean-pooled bi-encoder; the maximum is what lets one query word find its own evidence. The score never falls when a document gains vectors, and a search over part of the vectors gives a lower bound, which is how ColBERT and ColBERTv2 retrieve from a whole collection before scoring exactly. Its costs are in compute, a factor of $N_q$ over a bi-encoder per document, and above all in storage, a vector per token, which ColBERTv2 cuts to 20 or 36 bytes per vector with centroids and quantized residuals. On Cranfield, far from its training data, the pretrained ColBERTv2 was even with BM25 and with the unit's bi-encoder, and per-token matching ordered query 185's experimental study and review as a single vector did not.
A vector per token is one way to keep the detail that one vector loses. The other is to keep the vocabulary itself as the basis and learn weights for it, which is Learned Sparse Retrieval. Combining such representations with BM25 in one result list is the subject of Hybrid Retrieval.
References
- Khattab, O., and Zaharia, M. (2020). ColBERT: Efficient and effective passage search via contextualized late interaction over BERT. In Proceedings of SIGIR 2020, 39–48. https://doi.org/10.1145/3397271.3401075. arXiv:2004.12832. record
- Lin, J. (2021). A proposed conceptual framework for a representational approach to information retrieval. SIGIR Forum, 55(2), 1–29. https://doi.org/10.1145/3527546.3527552. arXiv:2110.01529. record · 2 pages
- Lin, J., and Ma, X. (2021). A few brief notes on DeepImpact, COIL, and a conceptual framework for information retrieval techniques. arXiv:2106.14807. record · 2 pages
- Santhanam, K., Khattab, O., Saad-Falcon, J., Potts, C., and Zaharia, M. (2022). ColBERTv2: Effective and efficient retrieval via lightweight late interaction. In Proceedings of NAACL 2022, 3715–3734. https://doi.org/10.18653/v1/2022.naacl-main.272. arXiv:2112.01488. record
- Stanford Future Data Systems (2025). ColBERT (software), commit
cc4f3dc91c0b45d2d08c251d9d95178285c65f1c:colbert/modeling/colbert.py,colbert/modeling/tokenization/,colbert/indexing/codecs/residual.py,colbert/indexing/collection_indexer.py. https://github.com/stanford-futuredata/ColBERT record - colbert-ir (n.d.). colbert-ir/colbertv2.0. Model card and
artifact.metadataat revisionc1e84128e85ef755c096a95bdb06b47793b13acf. https://huggingface.co/colbert-ir/colbertv2.0 (accessed 18 November 2026). record