Quantifying and Expanding the Theoretical Capacity of Late-Interaction Retrieval Models

Late-interaction retrieval models, such as ColBERT, represent documents and queries as sets of embeddings and use the MaxSim (Chamfer) similarity function to compute relevance. While these models consistently outperform single-vector dense retrievers, the theoretical reasons for this performance gap have remained poorly understood. This paper provides a formal theoretical framework for MaxSim, demonstrating that it is fundamentally more expressive than standard inner-product-based retrieval.

The authors prove that MaxSim similarity can exactly replicate the inner product of any two non-negative k-sparse vectors using only O(k) representation space. This result establishes that late-interaction models inherently possess the representational capacity of standard non-negative single-vector retrievers. Furthermore, the authors prove a separation: no finite-dimensional single-vector inner product can exactly preserve the inner products of arbitrarily high-dimensional sparse vectors, whereas MaxSim can.

However, the paper identifies a critical limitation: standard MaxSim cannot exactly replicate inner products between arbitrary real-valued vectors. To overcome this, the authors introduce Signed MaxSim, which decouples vector entries into magnitude and sign components. This extension allows the model to perform exact real-valued inner product computations. Additionally, the authors show that MaxSim can function as an evaluator of positive Conjunctive Normal Form (CNF) logical expressions, connecting neural retrieval to traditional Boolean search.

To validate these findings, the authors introduce a model called Fallon that utilizes Signed MaxSim. In experiments on synthetic datasets featuring negation-heavy queries, Fallon significantly outperforms the standard ColBERT baseline. Specifically, on negation-only queries, Fallon achieves an nDCG@10 of 0.788 compared to 0.008 for the baseline. These results confirm that the ability to natively handle negative values and complex logical constraints provides substantial robustness, particularly in out-of-domain settings where standard models struggle to suppress irrelevant features.