How Multi-Vector Retrieval Works at Scale

So today we have Marek Galovic and he is going to be talking about late interaction. And late interaction is a super underrated tool in your like retrieval toolkit that I think is not used that often. And not that many people know about it, but it's super effective. Every time I've used it, it's made things dramatically better. And so Marek is going to be talking about this and diving deep into the subject so you can see if it's right for you.

Thanks for the intro. So yeah, as Hamel mentioned, I'm going to talk about late interaction, how we scaled it, why it's actually useful, why it's better than single vector can also like help you in your retrieval pipelines and agents. So very quickly about myself. So I'm like CEO and co-founder of TopK, like the company that I started. Generally, I spend some time doing research on information retrieval, games, game theory, and like adversarial machine learning, mostly in computer security. Before that, I spent 3 years at Pinecone sort of leading their data plane and control plane engineering and teams. And before that, I was at Shopify, mostly working on risk algorithms, financial forecasting, and stuff like that. And so I would actually like to get started with like a pretty quick primer on single vector embeddings to sort of frame, frame the conversation around multivector. And so on a super high level, like for single vector, you take a bunch of tokens. It could be text tokens. It could be image tokens. Pass them through an encoder model, which mostly contextualizes the tokens within the document. And then like the important part at the end, like you take the token level representations and you pool them, right? And that pooling can be mean pooling. That pooling can be like last token pooling. You can take different models, use different strategies. The important part is like you pull into a single vector representation. And so sort of what this does is sort of allows you to take one model and create document-level representations and query-level representations independently, right? So you can pre-embed your corpus, you can ingest that into your vector DB or an index, you can store it there. And then at query time, you basically use the same model, embed a query, and then you retrieve the most similar documents based on dot product similarity. And dot product really can be like literal dot product. It can be cosine similarity. It can be Euclidean. Like all of those are really dot product-based metrics. And so like this sort of pooling at the end is sort of a lossy summary of the whole document in few thousand dimensionals. What this does to the document is sort of captures the high-level semantics and sort of the broad topical meaning of the document, but it really loses like the low-level detail that's generally required to answer like the very low-level precise queries. And so So this sort of is very adversarial behavior to agents because humans tend to like do very broad topical queries. And then like once they find the documents that they're looking for, they just dive in and then read it, right? This is very different from agents that like try to issue many very specific queries in parallel. What happens when you like use single vector retrieval, so like single vector embeddings in that setting, is that the agent issues a bunch of queries and then the retriever based on single vector embeddings just retrieves mostly the same documents, right? So you're sort of Not getting like the specificity that the agent was asking for. And you're mostly getting the same data. And this is precisely because like the low-level detail is lost and you're just capturing the high-level semantics. Other issue with that is that agenting retrieval is like sequential process, right? So you're generally not doing just single hop of retrieval, getting, getting a bunch of chunks and like producing an answer. You generally do multiple loops. It's a sort of sequential process. And then at the end, you sort of verify and try to produce an answer. This sort of setting means that like every retrieval and like noisy, noisy retrievals in every step sort of compounds the error over time. And so that can actually like derail the whole research process, especially if it happens like very early on. Like, this is not sort of like an engineering thing you can work around. Like, it's a theoretical limit. There's a paper from Google DeepMind that sort of shows that with single vector embeddings, you cannot really capture arbitrary relevance matrices, right? So for very simple cases, you actually need Either like weird dimensionality or it's just impossible to capture the relevance metrics. And so sort of that naturally leads to multivector embeddings. Before that, like there's workarounds, like people try to do hybrid search. People try to like combine keyword search with vector embeddings and then sort of do rank fusion or score fusion. Those are like approximations for what you actually want, right? You sort of want to capture the low-level details of the document. Very similar picture to the previous one. Basically, I just chopped off the pooling layer at the end because on a super high level, that's what multivector embedding is. You take your documents, take the like image patches, take the tokens, pass them through an encoder model, and then like out comes the token level representations, right? So it's sort of the encoder model contextualizes them and you produce multiple embeddings at the end. And this is sort of like very simple idea at the high level. And sort of the intuition for it is that, hey, let's just keep one embedding vector per document or per query, and then use that instead of like pooling at the end. And similarly, like scoring also works at this level. So you sort of try to capture the relevance between every query token and every document token and at a low level, and then aggregate that score to like a scalar that you can use to sort of rank documents relative to each other for like one query. What's super nice about it is that sort of it preserves the low-level detail. And generally multivector works much better on like out-of-domain, out-of-distribution retrieval and on long context documents. Similarly for like agent ping benchmarks, I'll show at the end, like it performs much, much better. We can just like use this. Have better retrieval and like be done with it. Unfortunately, no. Like since you are keeping one representation per token and you can have like hundreds of tokens or thousands of tokens for images, you are storing like 10 to 100 times more data per document because of this low-level representation. And similarly, scoring for a single vector, your scoring is just a dot product, right? So that's very fast. There's approximate indexes for that. It's sort of mostly solved problem right now. For multivector, the scoring is basically a matrix multiplication with some aggregation on top of that. So generally it does like 3 orders of magnitude more FLOPS per, per score. And this sort of like storage and compute overhead really makes it like impractical to work, to work with because one, like you need to produce the embeddings that are really large. So that's sort of like an engineering challenge of, okay, like I need inference engine that's fast enough. I need a network transfer protocol that's efficient enough to like transfer a large amount of data. Then I need like my indexing and retrieval to be just capable of storing that efficiently and like with a reasonable cost. And then like, I need retrieval that's fast enough to actually like score meaningful number of documents. Doing exact match sim, even on a few thousand of documents on a CPU, it just like gets impractical very fast. And so there are existing approaches like Plight, Warp, Muvera, like people try to work around this. There are generally trade-offs, like since, since you have so much data to work with, you need to compress that very heavily. And usually Plight and Warp, that compression generally relies on you having the data upfront and then precomputing really like IVF-PQ indexes or like Product quantizer indexes on top of that. And this really means that it's very hard to update the data on the fly, right? Because you're sort of getting the quality and the speed and trading off the operational complexity because you cannot update it. It's hard to do filters. It's hard to do stuff that you actually like need in production. And so that sort of poses the question, okay, can we actually do something different to make it both fast at scale and also very practical to use in like a day-to-day setting where like you need updates, you need filtering, you need all these things. And so we thought about it and we sort of came up with a new algorithm recently. Let's take the non-constant amount of work, which is sort of this matrix multiplication when you have variable number of query tokens, you have variable number of document tokens, and we need to compute maximum on top of that. Can we transform this sort of operation into a constant amount of work, right? So can we in some way compress these 2 sets and create a representation that like approximates the score, but it's like much cheaper to compute. The idea for that is like, we call it sparse multivector encoding. And basically on a high level, like we create sparse representations of document and query sets, document and query multivector embeddings. And then sort of the dot product between the sparse representations approximates Maxim, right? And so I will go over an example of how we actually do this. It's based on like random projections with sparsification, but what it enables is sort of very efficient retrieval at scale, because basically the retrieval is really inverted posting list, similar to like BM25, right? Like lexical search. And so we can like very efficiently compute the dot product at scale. And also the cost of this scales with the number of non-zeros in the sparse vector and not the ambient dimension, right? So we can create like hundreds of thousands of dimensional representations that are mostly zero. So we only pay for storage for the non-zero elements. And so how this actually works in practice is that we start with some like representation, right? This could be a document, this could be a query. And so we have 7 tokens here. And then just for an example, we have 4 dimensions for each token. Next step, we sort of create, like we project this set into a high-dimensional vector. So sort of going from 4 to like n dimensions, and can be like tens of thousands. And then we sparsify, right? So for most of the dimensions will just be 0 and we select just few top k non-zero dimensions for each token in the representation. And that's the first step, or actually like a second step. So first step, we started remembering. And then in the third step, we aggregate the token-level sparse representation Into like a document-level sparse vector, and that aggregation really is it can be sum for documents. It's like a sparse mean for queries, but that generally sort of compresses the multivector representation into a single sparse vector that has this property that dot product between query and document sparse vectors approximates maximum. This is the algorithm behind it, but it's really just solving the problem of I have a billion documents. I quickly need to prune the billion into few hundred the most promising ones, right? Like I'm not claiming we are computing exact maximum. I'm claiming we are computing approximate maximum. And so this sort of first stage solves recall. You find the candidates, but they don't necessarily have the same ranking as if you were to sort of compute with the exact maximum. And so then the second stage, we need to refine the candidate set with full maximum to basically recover the final ranking and give you like the final K results that you asked for. And so this is like the first step of the, what the search engine handles is sort of taking the set of all the documents. pruning it down to a few promising candidates and then re-ranking the candidates into the final top-K the client asked for. There's other stuff around it. So like you need inference for the models, you need quantization for the documents because they're still fairly large. As I mentioned, you need filtering, you need online updates, you need multi-tenancy, you need isolation, you need scaling, you need all these things. So it's sort of taking the algorithm and making that production ready. That's sort of like what TopK does for you out of the box. And then what it is like, it's fully managed, so you can just Take the data interested in, we'll handle the stuff for you. Since multivector is still like 2 to 3x, even with compression larger than single vector, like we built it on object storage. So it's much cheaper to just store the data. You can basically scale to unlimited amount of documents natively. Point of this talk, like we support late interaction, which is big difference between like TopK and other engines. We also support dense and sparse. So like dense and like learned sparse vectors out of the box. We support standard like lexical search with BM25, filtering, custom scoring. So you can sort of combine your Multivector score and then prioritize more recent results or maybe like closer results in terms of like geo distance. You can sort of define your scoring function as an algebraic expression. And generally we, we can get sub-100 millisecond tail latencies or P99 latencies at billion scale. That's for lexical search. That's for standard vector search or like late interaction. Sort of scale, scale for all these types of retrieval. And like exposes Python, JavaScript, Rust SDKs natively. And then we have SQL and STIG interface. Like Elastic is in the process of but SQL and Elastic interface on top of that. So you can very easily integrate with your existing stack. And so this is sort of like the architecture where it sits. We sort of, this is your clients or your application. Like we built the retrieval engine, which is the one part that sort of handles the storage, the indexing, the scaling, and the queries. And we also have our own inference engine that handles mostly multivector inference very efficiently. And this is built on top of like standard cloud. So sort of VMs, object storage, and GPUs. Zooming in, I have a separate talk you can find on Carnegie Mellon University university, it sort of goes more into details of how we build the database itself. Also happy to answer any questions about that. Generally, like the approach is one, separate compute from storage, right? So object storage is the only durable layers. You only pay for that storage and it's super cheap. And then on top of that, we have a stateless compute layer that handles all the like read/write operations. And then the second important thing is we also separate read path and write path, right? So when you write, generally like general search engines, when you ingest a lot of data, the node starts like indexing, starts processing the writes, and that can negatively impact your query latencies. And so we sort of separated the compute resources for writes and reads onto separate compute pools. And what that enables is we can handle like 70 megabytes per second of writes to an index and basically keep serving that without negative impacts on query latencies. And similarly, like the end-to-end latency for this is basically once you write, your data is visible for queries within in like 700 or 800 milliseconds. We also support strong consistency. So like, if you really need strong write visibility, we can give you that with sort of like client-side guarantees. This is like the system. If you want to learn more, like I've written a, like a write-up on this on our docs. How does it actually work end to end? Our query latencies generally sort of, this is for sparse search, which is like the basis for Multivector. We can do sub-50 milliseconds or sub-45 milliseconds P99 at billion scale. So in that sense, it's very fast and it also like scales throughput to hundreds of QPS. But I mentioned about there being like a first stage, which is your sparse retrieval, and then you need to re-rank with exact maxim. Like we are not actually re-ranking with like F32 or sort of float maxim. Like multivector is very friendly to compression. So you can compress to 1-bit or 2-bit per dimension. And then basically use that as your sort of data source for re-ranking at the end. And so we implemented our own kernels to basically do that. And generally like the latency for a standard document, for example, if you had like whatever, 256 tokens per document, it's up 100, like maybe 20 or 30 microseconds per document. So it's like tens of thousands of documents per second per core that we can rerank inside the engine. And then similarly for like computing the sparse multivector encoding, if you think about it, like what it really does, it takes your 128-dimensional multivector embeddings, computes a projection into 32,000 dimensions or 128,000 dimensions. So it's like a sort of going from lower dimension to very high dimensional, like abstract concept space, then aggregates that projection, right? Or like the token level projections. And this is really like a matrix multiplication with some aggregation. And so we sort of compared, we need like an efficient way to do that, right? So we compared our like internal implementation that's CPU based and how it scales to basically implementing the same transformation in PyTorch and running that on CPU, which is sort of here, maybe like 200 documents per second, and then running the same PyTorch code on a 3090 GPU. Basically what this shows is we can match GPU performance with just 8 CPU cores inside the engine as well. The point is integrating all these pieces inside the engine to sort of give you the experience and like not having you to rebuild that for Multivector to be usable. In terms of quality, this is our like Multivector embedding models that's actually open source on Hugging Face. And so we looked at different domains from the Vidura datasets, like visual document retrieval that we parsed and converted into text and then looked at, okay, what's the retrieval performance for the same corpus using dense 8 billion embedding model, in this case, like QN3, and then using our 100 million multivector embedding model. What it shows, it really, we outperform in some cases, like outperform by 40% the dense embedding model with a very small multivector embedding model, like embeds. I know we benchmarked 1.5 billion tokens per hour on a single small GPU, right? So Like cost efficiency also improves when you use smaller models that are stronger at the same time. Similarly on BrowseComp, some of you may know BrowseComp is like an agent deep research or deep research benchmark. And the point of this and like what this chart shows is that you can take like BM25 or dense retrieval or multivector. And basically if you use multivector, like an off-the-shelf 120 billion open source model, you can match the performance of like a proprietary GPT-5 using much weaker retriever, right? So sort of your like agent Capability improves with a stronger retriever. And then obviously if you use a stronger retriever with a stronger model, like that compounds. So sort of you can get the best performance with the strongest model and the strongest retriever. Lastly, we looked at like OfficeQA Pro, which is enterprise research. The dataset is, I think, treasury bulletins for in the like past 100 years. And the queries are sort of paragraph-long research queries for the agent to go through. This sort of shows that you have like Gemini CLI, which is your like the standard agentic setup. Hey, let's just have a file system. Let's add all the data into the file system and let the agent like go through it. That works. It has 18% accuracy and like costs $6 per query. Then like, this is a paper from Databricks. So Databricks has their own like parsing to show that improved parsing actually improves the agenting performance. And it does, like the agent like improves the accuracy to 30% and reduces cost like 5 times, 4 times. And then we sort of took the same, same idea, but like used our internal research agents that we have. Based on the multivector retrieval and basically achieved like 42% answer accuracy. So the highest one using the same model and reduce the cost about 13 times. So it's like 50 cents, 50 cents per question. And this really shows the standard like file system with grep, glob, and like the file system tools and agents works. It works better than just dense for the reasons that I described. But basically if you have much better retriever, you can get much better performance at much lower cost, even for like agentic, agentic setups. And so, yeah, it's I think that's the last benchmark that I have. I'm happy to answer any questions.

All right, thanks for sharing. I'm gonna ask you some questions and I'll open it up if that's okay. So a question that keeps coming up is, I think people that are newer to multi-vector, this embedding approach, always want to ask, how come you can't just increase the dimensions of the single vector approach? Can you talk a little bit about that? Because that's a common objection people have in their minds.

That's like the paper that I referenced, the, the LIMIT paper from DeepMind. They basically show But the setting that they have is sort of very abstract. They really try to construct arbitrary relevance matrices, which is not really the setup you would have in practice. But basically, even if you scale the single vector dimension infinitely, you cannot capture any relevance matrix. The pooling is still lossy, and then the models are not utilizing the space fully. So even if you increase the dimensions to a few thousand, the embeddings are usually a low-rank manifold in that space. Maybe capturing the lower variance components in those higher dimensions, but mostly the embeddings are very low rank. And that's, by the way, also true for Multivector. It's only using like few, few dimensions for actual embeddings.

Another question is people want to try this out in their environments, like this approach. Okay, there's different parameters you could tune, and how should people think about those? Should they just have like retrieval evals and like hill climb on those? How do you start Do you find that you need to even do that? See in practice, what's your advice in practice? A lot of people asked about different parameters and how you choose them.

What are the parameters you have in mind?

Someone asked about dimensions, number of dimensions, you know, a common one. There might be other ones.

Yeah. So generally I'm like of the idea that the system should just work. So TopK actually doesn't expose that many parameters. Like we allow you to choose the quantization, which really by default, like the one that we use works very well, but you can choose it. Like that's a trade-off. As for dimension, most of the multi-vec models are 128, that they use the down-projection from the internal model state to 128 dimensions. That generally works pretty well. NVIDIA has some models that perform really well on the VidORA benchmarks, just like on visual retrieval, but they use 3,000 dimensions to do that. So it reduces the practicality even more. There's 3 axes. One is dimension. The other is you can prune the multivector set. So if you think about it, not all of the tokens are really the same importance. You will have some convex set of tokens that are extremes. Yeah. And then query tokens will only attend to those. And so you can actually prune the set of multivector embeddings to much smaller number without like hurting recall pretty much at all, like with a very, very small reduction in recall. So that's the second one. And the third one, what I mentioned, like quantization. So you can take the float32 or float16 and go down to int8 or 2-bit or 1-bit with also like no or very minimal loss in performance. And so those are like the 3 dimensions you can tune. Top-K implements the quantization out of the box. So you can just use that. We'll do it for you. In terms of dimensions, like that's whatever the model gives you. And then pruning right now, you also need to do on your ends and just like a client-side parameter. We have our like semantic index, which is managed multivector embeddings with multivector inference and like all of that. There we also handle it for you. So basically you just get the text in, text out interface. You send text documents, you send text queries, and we handle all of these things for you and basically give you the same performance as exact Maxim with the model would give you out of the box. So you don't have to worry about that.

What kind of things do people do, if anything, to customize the retrieval system for themselves to make it work really good?

You have to start with evals. That's the first thing is you actually need to be able to measure where you want to go. If you just vibe it, I mean, you can get better vibes from the system, but that's not systematic, right? So you need to set up evals that make sense for you, ideally on your private data, because that's really what matters is your use case, and then sort of try to hill climb that eval to a point where like this works. And you have like many tools, like multivector is a very strong basis. Keyword search still makes sense in some cases. Like multivector will basically do keyword but on like semantic level, so it can actually like— it's really like a hybrid between keyword and dense. So that sort of gives you capability out of the box. And then very much underappreciated thing that like many engineers do in like e-commerce and is actually relevance tuning. So you might know that, hey, this product is really highly ranked, this, this hotel is very like popular. Say I'm like on my phone and I'm looking for restaurants, like these restaurants are near to me, right? So like it doesn't make sense like for a very good restaurant or very relevant restaurants to be shown in Berkeley when I'm right now in San Francisco. Like I want restaurants that are near me. And so actually like tuning relevance for your use case and like combining the content-level relevance scores with sort of the quality scores, like user-level signals, and using that in your scoring is a very powerful way to optimize retrieval. But it's really like use case dependent. So to be able to do that, like you need a query engine that actually enables that out of the box. Otherwise, like there's hacks you need to do around it, which like then introduces a bunch of other complexity.

Sounds good. Anything else that comes to mind? Like relevance tuning is a good one. Any other kind of things that you see people add, like need to think about when they're searching that comes up a lot?

I would say like evals, start with evals. You need a direction, right? Uh, we do a lot of evals internally on different benchmarks and that's like what enables us to give you like something that works really well out of the box, but like being able to just measure and it goes the same for retrieval quality is the same for like database performance. Like you need benchmarks, you need evals to sort of know where you stand and like know if you're improving or regressing. I think a sort of systems engineering one-on-one and then being able to understand, okay, what relevant actually means for my domain. That's like, you can optimize relevance, but like you first need to define, okay, what it actually means. I think e-commerce and REXys people do that better than RAG people, but like the same, same sort of approaches apply.

All right. Thanks everybody.

Cool. Thank you.