Late interaction models, which represent documents using a set of vectors (and are therefore also called multivector models), have emerged as compelling alternatives to single-vector embedding models across a variety of applications in modern ML systems. While their empirical advantages have been observed for almost half a decade, they come with significant costs: their storage footprint is substantially larger, and retrieval latency is considerably higher, making them less attractive for several applications. This raises a natural question: when do we actually need late interaction?
In recent years, existing theoretical results have provided important insights into the expressive power of multivector representations, but do not directly answer this question in the context of retrieval—their most natural application domain. In this talk, we give an explicit answer to when and why. We construct a family of retrieval problems for which late interaction models provably exhibit an exponential gap in representation size over their single-vector counterparts. We then show how this construction naturally leads to a semantic retrieval benchmark exhibiting the same qualitative separation in real-world models deployed in practice.
Our result uses techniques from the theory of pattern matrices, illustrating how ideas from TCS can explain an empirical phenomenon in the world of ML and help direct future research. Finally, while deploying late interaction in real-world systems raises substantial challenges and has led to a rich body of engineering-focused work, we will delegate the how to a later time.
Bio: Sabyasachi Basu is a postdoctoral researcher at Microsoft Research Bangalore, where he is part of the DiskANN team, working on efficient retrieval and approximate nearest neighbor search. He earned his PhD in Computer Science from UC Santa Cruz in 2025, under the supervision of C. Seshadhri. His work focuses on bridging theory and practice in computing research across a spectrum of classical algorithmic problems, with a particular emphasis on large-scale graphs.
