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

This paper develops a theoretical account of late-interaction retrieval with MaxSim. It proves that MaxSim can exactly reproduce the inner product of any two non-negative k-sparse vectors using O(k) representation space, and can express similarities that standard inner products cannot represent in the same space. The authors introduce Signed MaxSim, which can exactly reproduce arbitrary real-valued inner products and extends MaxSim to signed evidence. They also characterize MaxSim as a soft-OR and positive-CNF evaluator. In experiments with negation-heavy retrieval, Signed MaxSim raises nDCG@10 from 0.597 to 1.000 under vocabulary shift and from 0.008 to 0.788 on negation-only queries.