UMass Paper Proves MaxSim Subsumes Sparse Inner Products

For a couple of years now the retrieval community has quietly accepted a bit of an embarrassment. Late-interaction models like ColBERT keep beating dense and learned-sparse baselines on out-of-domain benchmarks, and nobody has had a clean theoretical explanation for why. A new UMass Amherst paper on Hugging Face by Julian Killingback, Varad Ingale, Hamed Zamani and Cameron Musco takes a swing at that gap.

Their central result is a construction. MaxSim, the sum-of-maxes similarity that ColBERT-style models use, can exactly reproduce the inner product between any two non-negative k-sparse vectors using only k query embeddings and k+1 document embeddings in three-dimensional space. That is a strong statement: anything a non-negative single-vector retriever like SPLADE or BM25 can express in inner-product form, a late-interaction model can express with representation size tied only to the sparsity. The authors also prove the other direction. With a sparsity-preserving encoder and a fixed embedding dimension, standard MaxSim cannot recover signed inner products at all. Their proposed fix, called Signed MaxSim, splits each vector entry into magnitude and sign and reintroduces the sign after the max, and they prove this extension can replicate any real-valued inner product.

The empirical stake they plant is small but pointed. On a retrieval task with queries containing negations, the authors report Signed MaxSim lifts nDCG@10 from 0.597 to 1.000 under a vocabulary shift and from 0.008 to 0.788 on negation-only queries against a standard ColBERT/MaxSim baseline. The intuition they give is straightforward: a signed similarity lets a query directly reduce the score of documents that contain a negated concept, which the standard non-negative construction structurally cannot do.

The honest caveat is that this rests on a single negation-centric evaluation, and existence of a construction does not guarantee a learned model will find it during training. The paper also does not settle what Signed MaxSim would cost in index size or query latency at production scale, which is what any team running ColBERT-style retrieval will actually care about. The forward-looking read: if the theorem holds up, teams whose users routinely search with negations now have a well-motivated architectural knob to turn.