ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT
Omar Khattab, Matei Zaharia
cs.IR, cs.CL
2020-04-27
ColBERT encodes query and document separately, then scores with MaxSim. MS MARCO MRR@10 is 34.9, about 170× faster than BERT-base with 14,000× fewer FLOPs.
Around 2019, concatenating a query and a document through BERT and scoring the [CLS] token pushed MS MARCO MRR@10 from the high twenties into the mid thirties. Every query-document pair had to run through a deep Transformer. Nogueira and Cho's BERT-base reranker of the official top-1000 took about 10,700 ms and 97T FLOPs per query; BERT-large took 32,900 ms. An extra 100 ms already hurts user experience and revenue. That cost is hard to serve.
Single-vector encoders can precompute documents, but they drop token-level matching and lag in quality. The live choice looked like expensive-and-accurate versus cheap-and-coarse.
ColBERT uses late interaction. Queries and documents are encoded separately into bags of contextual vectors. Interaction is delayed until a cheap, pruning-friendly step.
One BERT is shared. Inputs are marked [Q] or [D]. Queries shorter than Nq=32 tokens are padded with [MASK], a query-augmentation trick that lets the model write matchable expansions at those positions. Documents are not padded that way, and punctuation embeddings are dropped. A linear layer with no activation reduces BERT's hidden size to m=128, then L2-normalizes so a dot product is cosine similarity.
The score is MaxSim: each query vector takes its maximum similarity against the document vectors, then those maxima are summed. The interaction has no trainable parameters. Training uses triples and pairwise softmax cross-entropy on the two scores.
Because document encoding does not depend on the query, 9M MS MARCO passages can be indexed offline. At rerank time the query runs through BERT once and MaxSim is batched against cached matrices. For end-to-end retrieval every document vector goes into a faiss IVFPQ index: each query vector retrieves neighbor documents, the union is uniqued, then exact MaxSim reranks that shortlist. The paper's end-to-end setup uses squared L2.
Reranking the official BM25 top-1000, Dev MRR@10:
| Method | MRR@10 Dev | Latency | FLOPs/query |
| KNRM | 19.8 | 3 ms | 592M |
| Duet | 24.3 | 22 ms | 159B |
| fastText+ConvKNRM | 29.0 | 28 ms | 78B |
| BERT-base | 34.7 | 10,700 ms | 97T |
| BERT-base (same loss) | 36.0 | 10,700 ms | 97T |
| BERT-large | 36.5 (Eval 35.9) | 32,900 ms | 340T |
| ColBERT | 34.9 (Eval 34.9) | 61 ms | 7B |
Against BERT-base that is about 170× lower latency and 13,900× fewer FLOPs. Of the 61 ms, query encoding plus interaction is 13 ms; the rest is moving cached vectors onto the GPU. The FLOPs gap grows with k: about 180× at k=10, 13,900× at k=1000, 23,000× at k=2000.
Retrieving top-1000 from all 8.8M passages, ColBERT reaches 36.0 MRR@10, above its own rerank 34.8, because recall is higher. Recall@1000 is 96.8 against Anserini BM25 at 85.7 and docTTTTTquery at 94.7. End-to-end latency is 458 ms. On TREC CAR, MAP is 15.3 for BM25, 31.0 for BERT-base, 33.5 for BERT-large, and 31.3 for ColBERT.
Storage compresses. Rerank with 128-d 4-byte vectors uses 286 GiB at 34.9 MRR; 24-d 2-byte vectors use 27 GiB at 33.9, a one-point drop. Indexing MS MARCO takes about three hours on four GPUs. Ablations that replace late interaction with a single [CLS] dot product, swap MaxSim for average similarity, or drop query augmentation all sit well below full ColBERT.
This is the starting point of the multi-vector retrieval line. The engineering claim is concrete: encode documents once with BERT, serve with a vector index plus a cheap MaxSim, and land near cross-encoder quality at tens of milliseconds instead of tens of seconds. Token-level retrievers and later compressors such as PLAID still sit on delayed, prunable interaction.
ColBERT does not beat BERT-large overall. Eval MRR@10 is 34.9 against 35.9. The trade is four orders of magnitude less compute, and the option to retrieve from the full collection without a BM25 first stage.
The 2019–2020 experiments use BERT-base. No instruction models, long documents, or multilingual collections. End-to-end 458 ms is still far above BM25's 62 ms, and faiss used every CPU core. Even 27 GiB is large next to an inverted index. MaxSim searches independently per query term; the paper does not show that this is the right decomposition of relevance. TREC CAR is initialized from a BERT-large trained to avoid Wikipedia leakage, so it is not a clean clone of the MS MARCO setup. Later work has cut storage and latency again. Read this paper as the paradigm, not as today's numbers.