ReadPaper Blog
Quantifying and Expanding the Theoretical Capacity of Late-Interaction Retrieval Models
This paper studies why late-interaction retrieval models such as ColBERT, which score query-document pairs with MaxSim, can outperform single-vector dense and sparse retrievers. It proves that MaxSim can exactly reproduce inner products for non-negative sparse vectors using only O(k) representation space, introduces Signed MaxSim to handle arbitrary real-valued vectors, and connects these results to retrieval behavior involving long-tail matching, Boolean logic, and negation.
Source: Quantifying and Expanding the Theoretical Capacity of Late-Interaction Retrieval Models
Why late-interaction matters
The paper asks a theoretical question behind a well-known empirical pattern in neural information retrieval: why do late-interaction models using MaxSim often beat single-vector dense retrievers such as DPR and learned sparse retrievers such as SNRM or SPLADE. In standard single-vector retrieval, both query and document are compressed into one fixed-dimensional representation and compared by an inner product, whereas late-interaction models represent text as sets of embeddings and score relevance by summing each query embedding’s maximum similarity to document embeddings. The authors argue that the performance gap is not fully explained by giving late-interaction systems more representation space, because prior empirical work suggests that simply enlarging single-vector embeddings does not close the gap. Their central claim is that MaxSim itself is a more expressive similarity function than a plain inner product under important retrieval conditions. By formalizing MaxSim as a function over sets of vectors, the paper provides one of the first theoretical accounts of what late interaction can represent and why it can support stronger retrieval behavior.
MaxSim can mimic sparse matching
The core constructive result shows that MaxSim can exactly replicate the inner product between any two non-negative k-sparse vectors, even when the original vectors live in a possibly infinite-dimensional space. The construction uses O(k) representation space: the excerpt states that two k-sparse vectors can be encoded with exactly k query embeddings and k + 1 document embeddings in R3 while preserving their exact inner product. This matters because sparse retrieval is often built around matching weighted terms or learned lexical features, and many such signals are naturally non-negative. By proving exact reconstruction rather than approximation, the paper shows that late-interaction models can subsume the scoring capacity of non-negative sparse inner-product methods. The result also clarifies why MaxSim is not merely a heuristic token-matching operation, but a formal mechanism capable of representing high-dimensional sparse similarity through compact sets of low-dimensional vectors.
Why this beats plain single vectors
The paper goes further by proving a separation between MaxSim and standard vector inner products with the same representation budget. Its framework shows that there are similarities expressible by MaxSim that cannot be reproduced by a single fixed-dimensional inner product representation of equal size. This is especially relevant for retrieval over long-tail vocabularies, rare entities, and sparse signals, where compressing all evidence into one vector can discard distinctions among features that occur infrequently but matter for relevance. MaxSim avoids some of that compression because separate query and document embeddings can preserve local matching structure before aggregation. The implication is that late interaction can be theoretically more capable than single-vector retrieval not only because it stores more pieces, but because the maximum-over-document-embeddings operation changes what kinds of similarity functions are representable.
Signed MaxSim for negation
A limitation of standard MaxSim is that the non-negative inner-product replication result does not automatically extend to arbitrary real-valued vectors. The paper proves that, under the stated representation constraints, standard MaxSim cannot exactly replicate all real-valued inner products, which is important because negative weights can encode exclusion, contrast, or negation-like behavior in retrieval. To address this, the authors introduce Signed MaxSim, an extension designed to exactly reproduce any real-valued inner product. This modification preserves the late-interaction viewpoint while allowing positive and negative contributions to be represented in the similarity computation. The empirical evidence in the excerpt focuses on retrieval tasks involving negation, where Signed MaxSim improves out-of-domain performance over a standard ColBERT/MaxSim baseline, including nDCG@10 gains from 0.597 to 1.000 under a vocabulary shift and from 0.008 to 0.788 on negation-only queries.
What the paper concludes
The paper’s broader conclusion is that MaxSim provides a provable expressivity advantage over ordinary inner-product retrieval in several regimes. For non-negative vectors, MaxSim is at least as capable as standard vector inner products, and for arbitrary real-valued vectors, Signed MaxSim extends that parity to the full inner-product setting. The authors also show that MaxSim can act as an aggregation of soft-OR operations and as an evaluator of logical expressions in positive Conjunctive Normal Form, linking modern late-interaction retrieval to classical information retrieval ideas such as term matching and Boolean logic. These theoretical links help explain why models like ColBERT can perform well in out-of-domain retrieval, where exact local matches, rare features, and compositional evidence can be decisive. The paper therefore reframes late interaction as a mathematically richer retrieval architecture rather than only an engineering compromise between sparse matching and dense semantic search.
