MaxSim Is Strictly More Expressive Than Dense Retrieval, Provably

The field has treated late-interaction models like ColBERT as an empirical curiosity: better in practice, but without a principled explanation for why. That framing turns out to be wrong, and the gap runs deeper than benchmarks suggest.

MaxSim, the similarity function at the heart of late-interaction retrieval, is not just competitive with inner-product-based dense retrieval. It is strictly more expressive. By construction, MaxSim can exactly replicate the inner product between any two non-negative k-sparse vectors using only O(k) representation space. Think of it as a soft-OR aggregation over token-level matches: each query token votes for its best document match, and the sum of those votes can encode arbitrarily complex sparse similarity patterns that a single vector dot product cannot capture in the same space budget. Where dense retrieval compresses everything into one fixed-size vector and loses the ability to distinguish which parts of a document matched which parts of a query, MaxSim preserves that compositional structure. There also exist similarity functions MaxSim can express that standard inner products with identical representation budgets cannot, a ceiling dense-only retrieval cannot escape by scaling alone.

The paper also identifies a gap in standard MaxSim: it cannot exactly replicate arbitrary real-valued inner products because it is constrained to non-negative similarity contributions. The fix is Signed MaxSim, which extends the formulation to handle negative values by decomposing similarity into positive and negative components. This closes the expressivity gap completely. On a retrieval task with negation queries, specifically queries like "documents about X but not Y," Signed MaxSim lifts nDCG@10 from 0.008 to 0.788 on negation-only queries and from 0.597 to 1.000 under vocabulary shift, compared to a standard ColBERT baseline. For teams building retrieval systems over specialized corpora with logical or negation-heavy queries, the takeaway is direct: the expressivity ceiling of your similarity function is no longer a theoretical abstraction, it is a measurable performance gap you can close by switching the aggregation operator.

We're thinking: We find the most consequential part of this work to be what it rules out, not what it enables. Dense retrieval scaling, whether through larger encoders, better training data, or matryoshka compression, cannot escape the expressivity ceiling that a fixed-size inner product imposes. This proof means that teams investing heavily in single-vector dense retrieval infrastructure are optimizing inside a bounded space, while late-interaction models operate in a strictly larger one. The practical contradiction is that ColBERT-style models are still treated as the expensive option to avoid, yet this paper shows the architectural trade-off is asymmetric: you can always reduce late-interaction to dense retrieval behavior, but not the reverse. That asymmetry should shift how retrieval infrastructure decisions get made, especially for domains where query semantics involve composition, negation, or logical structure.

Key takeaways:

• MaxSim is formally proven to subsume inner-product similarity for non-negative vectors, and Signed MaxSim extends this to all real-valued vectors, making late-interaction strictly more expressive than dense retrieval at equivalent representation cost.
• Signed MaxSim achieves nDCG@10 of 0.788 on negation-only queries versus 0.008 for standard ColBERT/MaxSim; the result holds under vocabulary shift but is tested on a single negation-focused retrieval task, so generalization to broader corpora remains to be validated.
• Teams building retrieval pipelines over domains with logical queries, negations, or compositional information needs should treat Signed MaxSim as a drop-in upgrade to standard MaxSim and re-evaluate whether single-vector dense retrieval is the right architectural baseline at all.

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