PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Julian Killingback, Varad Ingale, Hamed Zamani, Cameron Musco

arXiv:2607.05803v1cs.IR

TL;DR

The theoretical representation power of MaxSim and its relationship to inner-product retrieval remain insufficiently understood despite strong empirical performance. This paper proves MaxSim's expressive capacity, introduces Signed MaxSim for real-valued inner products, and shows that late-interaction similarities can subsume inner products while also expressing logical operations beyond them.

  • Problem

    Despite strong empirical performance, the theoretical representation power of MaxSim and its distinction from inner-product retrieval remain insufficiently understood.

  • Method

    The paper constructs low-dimensional vector sets for MaxSim, introduces Signed MaxSim, and analyzes MaxSim's connections to sparse inner products and Boolean logic.

  • Results

    MaxSim exactly reconstructs non-negative k-sparse inner products, separates from finite-dimensional single-vector embeddings, and evaluates positive conjunctive-normal-form expressions.

  • Takeaways & Limitations

    Late-interaction retrieval has at least the representational capacity of non-negative inner-product retrieval while supporting infinite-dimensional sparse representations and Boolean-logic-aligned similarity.

  • Takeaways & Limitations

    Whether decoupling the number of embeddings from sparsity would let standard MaxSim exactly replicate real-valued inner products remains open.

Abstract

from arXiv · show

Late-interaction retrieval models that use the MaxSim similarity function have shown strong empirical performance, often outperforming single-vector dense and sparse retrieval models. Despite these empirical findings, little is known about the theoretical representation power of MaxSim and how it compares to other retrieval approaches. This paper shows by construction that MaxSim similarity can exactly replicate the inner product between any two non-negative k-sparse vectors with possibly infinite dimension, requiring only O(k) representation space. Moreover, there exist similarities that MaxSim can express while standard vector inner products with the same representation space cannot. Leveraging our theoretical framework, we introduce Signed MaxSim which allows late-interaction models to exactly replicate any real-valued inner product, something we prove standard MaxSim is not capable of. We 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. Our findings show that MaxSim is at least as capable as standard vector inner products for any non-negative vectors and our extension, Signed MaxSim, is as capable for any vectors. Both similarities possess additional capabilities that inner product cannot replicate, marking one of the first theoretical justifications and quantifications of late-interaction methods. Our theoretical findings are supported empirically: on a retrieval task featuring queries with negations, Signed MaxSim improves out-of-domain performance significantly over a standard ColBERT/MaxSim baseline with nDCG@10 increasing from 0.597 to 1.000 under a vocabulary shift and from 0.008 to 0.788 on negation-only queries.

1 Introduction

The introduction argues that late-interaction retrieval succeeds not merely through additional representation space but through the greater expressivity of MaxSim. It presents results showing that MaxSim subsumes nonnegative inner products, separates from finite single-vector embeddings in high-dimensional sparse spaces, and supports Boolean-style logical evaluation.

  • Dense and learned sparse retrievers encode texts as single fixed-dimensional vectors and estimate relevance with inner products, whereas ColBERT-style late interaction represents texts as embedding sets.
  • Late-interaction models have shown superior empirical performance, especially out of domain, and this advantage is not explained by additional representation space alone.Giving single-vector approaches more embedding dimensions has diminishing returns and does not match late-interaction performance.
  • MaxSim exactly reconstructs inner products of nonnegative vectors, including k-sparse vectors, using k query embeddings and k + 1 document embeddings in R3.The construction applies to both sparse and dense vectors, including sparse vectors from high-dimensional spaces.
  • No single finite-dimensional vector embedding can preserve inner products for k-sparse vectors from an arbitrarily high-dimensional ambient space, while MaxSim preserves them with size-k vector sets in R3.
  • MaxSim aggregates Soft-ORs and acts as a rank-equivalent evaluator for negation-free Conjunctive Normal Form expressions.This supports matching synonyms and multiple forms of a relevant concept without overly rewarding repeated surface forms, while connecting neural retrieval to Boolean search.

2 Related Work

Prior work established late-interaction retrieval through ColBERT and MaxSim, while addressing its indexing and retrieval costs. Theoretical analyses have focused mainly on the capacity and compression limits of dense single-vector retrieval models.

  • Late-interaction retrieval: ColBERT introduced late-interaction retrieval with MaxSim, a similarity function applied between query and document token vectors.Late-interaction models gained prominence because of strong empirical performance.
  • Late-interaction retrieval: Storing one vector per document token creates large indexes and slows retrieval, motivating follow-up work on reducing these costs.The passage identifies index size and retrieval speed as key limitations of the original approach.
  • Theoretical analyses: Earlier theoretical work has primarily studied dense retrieval models that represent queries and documents with a single embedding and generally compare them using an inner product.This line of research includes analyses of errors introduced by compressing dense representations.

A. Standard MaxSim CANNOT DISTINGUISH THE DOCUMENTS

The section contrasts two open-source AI documents: one is irrelevant despite mentioning “Google,” while the other is relevant despite containing no Google mention. These documents illustrate a case that standard MaxSim cannot distinguish.

  • A. Standard MaxSim CANNOT DISTINGUISH THE DOCUMENTS: Doc 1 is labeled irrelevant even though it mentions “Google.”It is described as an open-source AI tool.
  • A. Standard MaxSim CANNOT DISTINGUISH THE DOCUMENTS: The contrast is between keyword overlap with “Google” and document relevance.Doc 1 has the mention but is irrelevant, whereas Doc 2 lacks the mention but is relevant.
  • A. Standard MaxSim CANNOT DISTINGUISH THE DOCUMENTS: Doc 2 is labeled relevant despite having no Google mention.It is described as an open-source AI toolkit.

B. Signed MaxSim S± SEPARATES ROUTING FROM SIGN

The section illustrates that standard MaxSim can mishandle negated constraints because its maximum operation routes each query token to an incidental positive similarity. In the example, both documents satisfy the positive request, but only Doc 2 satisfies the exclusion constraint.

  • Standard MaxSim: Standard MaxSim selects the largest raw similarity for each query token, even when the explicit “Google” similarity is negative.For both documents, the maximum instead selects the incidental similarity of 0.4 to “Open-source”.
  • Negated constraints: For “Open-source AI tools that do not mention Google,” both documents satisfy the positive request, but only Doc 2 satisfies the exclusion constraint.The example therefore distinguishes positive matching from correctly enforcing negation.

3 Late-Interaction Similarity for Exact Inner Product Computations

MaxSim exactly reproduces inner products for arbitrary-dimensional non-negative vectors using representation size tied to sparsity, with independently constructed encodings. Standard MaxSim cannot achieve the same for real-valued vectors, but Signed MaxSim extends the construction to recover arbitrary real-valued inner products exactly.

  • 3.1 Non-negative vectors: MaxSim exactly replicates the inner product between non-negative vectors, including countably infinite-dimensional vectors, with representation size tied only to their non-zero elements.The query and document representations can be constructed independently, preserving the asymmetric dual-encoder setting.
  • 3.1 Non-negative vectors: MaxSim can represent infinite-dimensional non-negative sparse vectors with space tied to non-zero elements, whereas a standard vector inner product with the same representation space cannot.This establishes additional representational capacity for MaxSim beyond standard inner products in this setting.
  • 3.1 Non-negative vectors: The construction maps sparse vectors to sets of dense vectors in R3, using quadratic polynomials whose maximum selects matching indices and contributes the corresponding product.Non-matching indices yield negative values, while a shared zero vector handles absent coordinates.
  • 3.2 Signed vectors: Standard MaxSim cannot exactly recover inner products between arbitrary real-valued vectors under sparsity-preserving representations, even with shared document embeddings.If the shared set contains the zero vector, MaxSim scores are non-negative and cannot recover ⟨−ei, ei⟩ = −1.
  • 3.3 Signed MaxSim: Signed MaxSim modifies the multi-vector representation and similarity function so arbitrary real-valued sparse vectors have exact inner-product representations.For ku-sparse u and kv-sparse v, the construction uses sets of signed R3 pairs with sizes ku and kv + 1.

4 The Dimensionality Bottleneck of Standard Inner Products

Standard inner products cannot exactly compress arbitrarily high-dimensional sparse vectors into a fixed finite dimension because of a rank bottleneck. MaxSim avoids this constraint by representing a k-sparse vector as k vectors in R3 using O(k) parameters while preserving exact inner products.

  • Problem: No finite-dimensional inner product space can exactly preserve inner products among arbitrarily high-dimensional sparse vectors.The section establishes this as a fundamental rank constraint on single-vector representations.
  • Method: The impossibility holds even with asymmetric query and document mappings into Rd.The proof reduces compression to embedding d+1 mutually orthogonal vectors into Rd.
  • Theorem 4.1: For any finite d, no mappings from d+1 standard basis vectors in R^(d+1) to Rd can exactly preserve all pairwise inner products.This is Theorem 4.1, the stated impossibility of dimensionality compression.
  • Proof: The contradiction follows because the required identity Gram matrix has rank d+1, whereas the mapped product has rank at most d.Writing the mapped vectors as columns of U and V gives U^T V = I_(d+1), but rank(U^T V) ≤ d.
  • Implication: Consequently, standard inner products require approximation for vectors drawn from an arbitrarily large vocabulary in fixed dimension.The rank bottleneck prevents exact compression of even d+1 orthogonal concepts into d dimensions.
  • MaxSim advantage: MaxSim bypasses the rank constraint by representing each k-sparse vector as a set of k vectors in R3 using O(k) parameters.This representation preserves exact inner products regardless of the underlying vocabulary size.

5 Late-Interaction Similarity as Logical Expression Evaluation

This section formalizes MaxSim as a fuzzy logical operator: its inner maximization implements weighted OR over alternatives, and grouped query vectors evaluate positive CNF expressions. For binary weights, the resulting similarity is rank equivalent to exact positive-CNF Boolean evaluation.

  • Weighted Max-OR: MaxSim’s inner maximization selects the strongest weighted matching term in an OR-clause, avoiding score inflation from multiple synonyms.Weighted Max-OR uses the maximum of document relevance weight times query importance weight across matching terms.
  • Positive CNF Evaluation: For binary weights, MaxSim exactly evaluates positive CNF logic without negations, producing document rankings equivalent to the strict Boolean scoring function.Theorem 5.2 maps a positive CNF query with h clauses to |Q| = h query vectors and maps each document to |D| + 1 document vectors.
  • Positive CNF Evaluation: In positive CNF evaluation, each satisfied clause contributes 1 and each unsatisfied clause contributes 0, so total similarity counts satisfied clauses.A document satisfying all h clauses scores h, while a document failing at least one scores at most h −1, preserving Boolean ranking.

6 Experiments

The experiments test whether Signed MaxSim’s ability to represent real-valued inner products improves retrieval on synthetic tasks involving negations and exclusions. Across vocabulary-shift and negation-only settings, Signed MaxSim substantially outperforms the standard ColBERT/MaxSim baseline.

  • Experimental focus: The study targets retrieval with negations or exclusions, where replicating real-valued inner products may provide an advantage.This directly evaluates whether Signed MaxSim’s theoretical capacities translate into empirical gains.
  • Experimental setup: Synthetic training and evaluation tasks isolate architectural effects while reducing confounding factors such as validation-test mismatch and limited training data.Queries combine required attributes with attributes that should not be present.
  • Experimental setup: 100k queries and 200k documents are generated for training, with one to four inclusion terms and exactly one negated term per query.Models use contrastive training with in-batch negatives, and queries are designed to limit the chance that in-batch negatives are true positives.
  • Evaluation benchmarks: Each evaluation benchmark contains 2,000 queries against 100k independently generated documents, covering in-domain, different-vocabulary, and negation-only settings.The different-vocabulary benchmark tests generalization to new features, while negation-only queries test generalization to new query formats.

7 Results and Discussion

Across in-domain and out-of-domain tests, Signed MaxSim substantially outperforms standard ColBERT/MaxSim, especially on vocabulary shifts and negation-only queries. The results attribute this advantage to Signed MaxSim’s ability to represent negative evidence and suppress misleading token matches.

  • In-Domain Results: Signed MaxSim significantly outperforms standard ColBERT/MaxSim across all measured in-domain metrics, despite ColBERT learning the synthetic task.Standard MaxSim can learn the task even though it does not naturally handle negative values needed for negations.
  • Out-of-Domain Results: On the Different Vocabulary dataset, Signed MaxSim improves over its in-domain result while ColBERT shows a substantial reduction.The contrast indicates that ColBERT relies heavily on shared training–evaluation features, whereas Signed MaxSim generalizes across the vocabulary shift.
  • Negation Only Results: ColBERT’s near-zero Negation Only performance indicates that it ranks documents containing the negated attribute above relevant documents.Because most of the 100k corpus is relevant for these queries, random retrieval would perform relatively well, making ColBERT’s result especially revealing.
  • Failure Mechanism: Standard MaxSim struggles with negation because producing a low query score requires all document embeddings, including unrelated ones, to score low.ColBERT learns to match some relevant feature, but negation-only queries provide no relevant aspect to match.
  • Signed MaxSim: Signed MaxSim resolves this failure by natively supporting negative values that penalize features, although Negation Only AP remains limited by evaluating only the top 1,000 retrieved documents.With tens of thousands of relevant documents, relevant items outside the top 1,000 contribute zero precision regardless of model quality.
  • Overall Discussion: Together, the three evaluation settings show that Signed MaxSim addresses standard MaxSim’s inability to encode semantic negations and relational patterns requiring suppression of token matches.ColBERT performs reasonably on aligned distributions but degrades dramatically after distribution changes.

8 Conclusion

The conclusion establishes that MaxSim matches or exceeds inner-product retrieval for non-negative vectors while using O(k) space to replicate infinite-dimensional sparse representations. It also identifies open questions about real-valued replication and future empirical directions for neural retrieval architectures.

  • Conclusion: MaxSim is at least as expressive as inner-product retrieval for non-negative vectors and can exactly replicate infinite-dimensional sparse representations using O(k) space.The work contrasts this with the impossibility of exact replication by standard finite-dimensional single-vector models.
  • Open questions: Standard MaxSim cannot replicate inner products between real-valued vectors when the number of embeddings is tied to the original vector’s sparsity.Whether decoupling the number of embeddings from sparsity enables exact real-valued replication remains open.
  • Future directions: Future empirical work could test whether trained models learn localized logical structures implicitly or benefit from explicit embedding regularization for out-of-domain generalization.The polynomial embedding constructions demonstrate that exact logical evaluation is geometrically possible within late-interaction spaces.
Loading 2607.05803v1…