Multi-Vector Retrievers (2021) › The Solution

Multi-vector retrieval systems addressed these limitations by fundamentally changing the unit of representation from documents to tokens. Instead of encoding a query or document as a single aggregated vector, these systems encoded each token in the query and document as its own contextualized embedding vector. This token-level representation preserved the semantic richness of dense embeddings while enabling fine-grained matching between individual query tokens and document tokens. The key architectural insight was that retrieval could operate at multiple levels simultaneously, matching token pairs while maintaining an understanding of semantic relationships through contextualized embeddings.

ColBERT (Contextualized Late Interaction over BERT), introduced by researchers at Carnegie Mellon University and the University of Waterloo, pioneered this approach. The system used BERT to encode each token in a query and each token in a document, producing contextualized embeddings that captured both the token's identity and its context within the sequence. For a query with $n$ tokens, ColBERT produced $n$ query token vectors. For a document with $m$ tokens, it produced $m$ document token vectors. The relevance score between query and document was then computed through "late interaction," matching each query token vector to the most similar document token vector, then aggregating these token-level similarities into an overall relevance score.

The late interaction mechanism worked by computing maximum similarity for each query token. For each query token vector $\mathbf{q}_i$, the system found the document token vector $\mathbf{d}_j$ with the highest cosine similarity, then summed these maximum similarities across all query tokens. This approach, formalized as $\sum_{i=1}^{n} \max_{j=1}^{m} \text{sim}(\mathbf{q}_i, \mathbf{d}_j)$, ensured that each query term found its best match in the document, regardless of where that match occurred. Unlike single-vector methods that required matching at the document level, or sparse methods that required exact token matches, late interaction allowed flexible matching between semantically related tokens while still operating at fine granularity.

BERT's contextualization enabled the system to distinguish a token's meaning in different passages. Each token vector captured the token itself together with its meaning in context. The token "bank" would have different embeddings in "river bank" versus "bank account," allowing the system to match semantically even when tokens didn't match exactly. Query tokens could match document tokens that were semantically related but lexically different, while still operating at the token level rather than the document level. This hybrid capability enabled multi-vector systems to handle both semantic similarity and lexical precision within the same framework.

The matching process in multi-vector retrieval systems was computationally more complex than single-vector methods, but this complexity was manageable through efficient indexing and approximate search techniques. Systems could pre-compute and index all document token vectors, enabling fast retrieval at query time. Approximate nearest neighbor search techniques like FAISS could be adapted to work with multi-vector representations, finding documents whose token vectors collectively matched query token vectors. The computational overhead compared to single-vector retrieval was significant, but the performance gains on many tasks justified the additional cost, especially as specialized hardware and optimized implementations became available.