Late Interaction and Multi-Vector Retrieval

The third paradigm

The corpus has taught you two ways to score a document against a query. Sparse retrieval scores one number per matching term against an inverted index. A dense bi-encoder compresses the whole document into one vector, compresses the query into one vector, and scores their similarity. There is a third, it has held state of the art on retrieval benchmarks for years, and almost nobody deploys it.

The axis that organizes all four options is when the interaction between query and document is allowed to happen.

Table

Reading down the first column is reading down a ladder of how much the model is allowed to know about the query when it looks at the document. The cross-encoder knows everything and can therefore precompute nothing, which is exactly why it is a reranker over a short list rather than a search index.

Paradigm	Precomputed before the query arrives	Computed per query	Indexable
Sparse (BM25)	term postings and statistics	a sum over matched terms	yes, inverted index
Dense bi-encoder	one vector per document	one dot product per candidate	yes, ANN index
Late interaction	one vector per document token	a max-similarity per query token	yes, with work
Cross-encoder	nothing at all	a full transformer pass per pair	no, rerank only

Sparse and bi-encoder are early interaction: the document representation is finished before your query exists. The cross-encoder is fully late and therefore unindexable, which is why the RAG architecture lesson could only ever put it over a candidate list. Late interaction is the middle rung, and the middle rung is where the engineering is.

MaxSim, computed rather than described

Keep one vector per token, for the query and for the document. Score a document as the sum, over query tokens, of that token's best match against any document token. That operation is MaxSim.

query tokens (3):    q1 = "error"   q2 = "code"   q3 = "E4711"
document A tokens (5), from a troubleshooting page for that code

similarity matrix (cosine, query rows against document columns)

           d1     d2     d3     d4     d5      row max
  q1     0.31   0.62   0.18   0.44   0.22       0.62
  q2     0.27   0.71   0.35   0.29   0.19       0.71
  q3     0.12   0.15   0.09   0.11   0.88       0.88
                                              -------
                              score(A) = 0.62 + 0.71 + 0.88 = 2.21

document B, a general page about error handling, same first two rows

  q1 row max 0.62
  q2 row max 0.71
  q3 row max 0.21     nothing in B is that identifier
                                              -------
                              score(B) = 0.62 + 0.71 + 0.21 = 1.54

  2.21 - 1.54 = 0.67, and 0.88 - 0.21 = 0.67
  the entire difference between the two documents is one row

Three properties fall out of that block. The score is a sum of per-query-token maxima, so one query token that matches nothing contributes near zero rather than dragging the whole score down. Each query token gets to pick its own best match independently, so a document does not have to be about the query on average, it has to contain the right pieces. And the difference between a document that has the rare identifier and one that does not is one row of a matrix, which is the property the next section is about.

Recovering the rare term

The RAG architecture lesson gave you this failure already: queries naming a rare error code come back with paraphrases about error handling, and the fix offered there was the sparse half of hybrid retrieval. That fix works and it has a limit. BM25 finds E4711 when the query spells E4711, and misses when the user typed a variant, or when the identifier appears in a table cell the tokenizer split, or when the match needs to be semantic and exact at once ("the timeout error on the payments callback" against a page that names the code and never uses the word timeout).

Late interaction covers that case without a second index, because the exact-match behavior is emergent rather than bolted on. The q3 row above is a semantic match against a specific token, so a near-variant of the identifier still scores high on that row while a page about error handling in general does not. This is the honest form of the argument for it: not that it beats hybrid retrieval everywhere, but that it puts the rare-term behavior and the semantic behavior in the same representation instead of in two systems whose scores you then have to fuse.

The storage bill

Now the reason nobody uses it. One vector per token is a lot of vectors.

corpus: 10,000,000 passages, 120 tokens each = 1,200,000,000 token vectors

dense bi-encoder, one vector per passage
  1,024 dims x 4 bytes            = 4,096 bytes
  10,000,000 x 4,096              = 40.96 GB

late interaction, one vector per token, 128 dims, float16
  128 dims x 2 bytes              = 256 bytes
  1,200,000,000 x 256             = 307.2 GB

  307.2 / 40.96                   = 7.5x the bi-encoder index

late interaction, 2-bit residual compression against a centroid,
plus a 4-byte centroid id per vector
  128 x 2 bits = 32 bytes, plus 4 = 36 bytes
  1,200,000,000 x 36              = 43.2 GB

  307.2 / 43.2                    = 7.1x smaller than uncompressed
  43.2 / 40.96                    = 1.05x the bi-encoder index

That last line is the one worth carrying out of this lesson. Compressed, a late-interaction index over this corpus is five percent larger than the single-vector index it replaces, and the 7.1x reduction the arithmetic produces sits inside the 6 to 10x that ColBERTv2 reports for its residual compression scheme. The technique is not expensive. Uncompressed late interaction is expensive, and the two get conflated constantly.

You will also hear that late interaction costs 50 to 100 times a single-vector index, and that number is not wrong so much as it is a different comparison. It is the comparison you get when both sides use the same dimension and the same precision: a 128-dim bi-encoder index over this corpus at float16 is 10,000,000 x 256 bytes = 2.56 GB, and 307.2 / 2.56 = 120x, which is the token-count ratio and nothing else. Production bi-encoders run at 768 to 3072 dims while token vectors run at 128, so the dimension gap absorbs most of the token-count gap before compression is applied at all. When someone quotes a multiplier, ask which two indexes are being compared.

PLAID: not loading what you do not need

Compression solves storage. It does not solve the scoring loop, which is naively a nested loop: every query token against every token of every candidate document. PLAID's move is to notice that the centroid ids are already there, and that they are enough to throw most documents away.

each document token vector is stored as (centroid id, 2-bit residual)

stage 1  represent each document as its BAG OF CENTROID IDS only
         score the query against centroids, not against residuals
         this is a cheap approximation: no residual is decompressed,
         and most of the index is never read

stage 2  keep the top candidates from stage 1, and only for those
         reconstruct token vectors from (centroid + residual)

stage 3  run full MaxSim on what survived

PLAID's authors call stage 1 centroid interaction, and sparsifying that bag of centroids centroid pruning. The reported effect is up to 7x faster on GPU and up to 45x on CPU against vanilla ColBERTv2 without impacting quality, reaching tens of milliseconds on GPU at 140M passages. The successor engine WARP reports a further 3x over the ColBERTv2 and PLAID engine, and 41x over the reference implementation of a related multi-vector retriever, again while maintaining retrieval quality.

Notice what that stage 1 is. It is the coarse quantizer from the ANN lesson, in a different costume: a cheap first pass over centroids that decides what the expensive pass is ever allowed to look at, with the same consequence that a bad first pass caps your recall no matter how much work stage 3 does.

Where it fits, and where it does not

Two places in a real pipeline. As a middle stage, between cheap first-pass recall and an expensive cross-encoder, cutting the candidate list the cross-encoder has to read. Or as a replacement for the cross-encoder, when reranking latency is the binding constraint: MaxSim over precomputed vectors is arithmetic, while a cross-encoder is a transformer forward pass per pair, and that is the gap that lets a late-interaction stage hold a tight latency cap at a candidate depth a cross-encoder could not.

Interview nuance: the honest verdict is that for most systems this is over-engineering. A bi-encoder plus a cross-encoder over the top 100 is the right answer for the overwhelming majority of RAG products, and an interviewer who hears late interaction proposed for a 200,000-document internal wiki will read it as a technique looking for a problem. Two situations flip that. A recall requirement high enough that first-stage misses are the dominant failure, where per-token representations recover what pooling averaged away. And multimodal page retrieval, where the page-image models from the parsing lesson emit patch vectors natively, so you are already holding a multi-vector index and late interaction is simply how you score it.

Recap: late interaction stores one vector per token and scores a document as the sum over query tokens of the best match against any document token, which is why a rare identifier survives when pooling would average it away. Uncompressed it is many times a single-vector index; with 2-bit residual compression against centroids it lands near parity, and the multiplier you hear quoted depends entirely on which two indexes are being compared. PLAID makes the scoring loop affordable by scoring centroid bags first and decompressing only survivors. It belongs between recall and a cross-encoder, or in place of one under a hard latency cap, and it is the wrong answer for an ordinary corpus.

Sources: ColBERT · ColBERTv2 · PLAID · WARP