Thank you.
All right.
Good afternoon, everybody.
Thank you for joining.
Yeah.
So today, we are going to talk a bit about how to do query processing for learns
parts models in a more efficient way than what you've seen so far.
We, my name is Antonio Ferdinand.
We work together at SELTS.
Those are our contacts, you know, for free to reach out.
Maybe like a few words about SELTS.
SELTS is a startup that is working on enabling essentially AI workflows and LLMs and chat
bots and foundational models in general to access the web as a tool.
So pretty much web knowledge through an API for any application that needs to run independently
autonomously and reliably, most importantly.
So I'm going to pass the mic to Ferdinand.
Yeah.
Hey, everyone.
Hi, for me as well.
I'm going to give a quick context.
Just a quick introduction.
I guess about what searches.
I'm sure most of you are all familiar and vaccine gave a nice quick introduction
but this might be relevant just to understand a bit of the intricacies of what Antonio will be talking
about later.
So in which context are we, we're talking about ad hoc search.
So we have some kind of big document collection.
For example, in this case, a bunch of documents talking about different open search frameworks
and maybe one random document about get codes and whatever.
A bunch of different other documents in this collection.
We pass this to some processor that will give us some impact scores or whatever
that we can then pass on to an index and then have some query that comes in.
And hopefully this index then gives us in this case maybe the top three documents.
And it should hopefully filter out for our query open source search framework.
It should detect that these three documents up here are the ones that are somewhat relevant.
And the one about get codes probably is not.
And so initially or what what we're going to look at in this case is quickly.
This what I call here a processor.
Originally and that's what Maxi Marty had a quick example for is usually we'd use some kind of
lexical term-based frequencies, whatever.
So for example, we have here just one processor that takes in the documents.
And in this example, perhaps the first document contains Lucine, the term Lucine or the word Lucine 10 times.
And that's just what we count.
We have some term frequencies.
Maybe is is in this document 15 times A a bunch of times as well.
And this is what we do per document.
We could do some more complex stuff, normalize them things like that.
But just for the sake of this example.
We're using term statistics to evaluate how important what the impact of one of these terms
and our documents is.
And what we then do in our index is we convert this into an inverted index.
And just use the terms as the posting and then have a postings list where every single term
we count which document contained this term and then have our impact score inside there.
So in this case maybe the term frequency we had Lucine 10 times.
Some other document in our collection document 17 has two times.
But now in this case the list is sorted.
So any document in between doesn't actually contain this term.
And we can use this to quickly search through our corpus by we get a new query.
Maybe we only need to look at the posting list that contain these queries.
That's how search per say works very quickly.
Nice thing about this terms terms statistics at least it's very very fast.
We can use tokenizer for example to tokenize documents very very fast.
We can index stuff very fast and it's very fast and retrieval.
There's been years of optimizations and research to make this really very quick.
And it's actually fairly effective.
I mean BM25 is still being used today and it's fairly hard to beat still.
Like we even the big neuromodals are somewhat better on some few tasks.
But in the end these terms statistics are very effective.
Some of the downsides which we'll talk about in a second what neuromodals maybe do give us is.
In this case we only have lexical matches.
We don't have any semantic matching we only have or can only find the documents that actually contain the terms that we're searching for.
We could do some complex document expansion and this and that.
But in the sense in this case right here we only have lexical matches we can actually work with.
And the final negative maybe is these are a heuristic.
We have a few parameters in BM25 we have two parameters where we might be able to change the scores a bit.
But in general we have some heuristic that we're using to assess the impact of a score it's not learned and what we've seen in the past few years using models to learn scores maybe a bit better.
So what happens yeah BM25 back yeah almost or more than 20 20 years ago now.
Pretty much yeah a couple of things were developed in between but since Bert was created a bunch of different learned sparse models were created.
Which yeah it's it's a it's a whole zoo and different types of variations and things like that but in the end they all kind of do a very similar thing or try to achieve similar things.
And I'll try to summarize that in this quick slide where for the sake of this example let's just look at the first document here and we'll do our processors now doing some magic in some neural magic in the background.
And instead of having yeah terms to this six what we're doing is we're trading the model to compute impact scores for the terms in our document so this 13.5 for example is just some.
Score that the model learned this is.
The relevance or the impact of this term in our document and it's able to learn for example that is an A and stop words or words that don't encode semantics they might not have high impact scores because they don't encode.
A lot of information that might be relevant and the last part is they may actually be able to add semantically similar terms that yeah get aren't actually in the document they can add terms to be able to find documents that don't actually contain terms.
Yeah avoiding this lexical mismatch problem so these are two advantages that these neural models give us on the one hand.
Learnable impact scores on the other hand semantic term expansion the downside is it's very very slow and expensive building a web scale index or something with these types of models they're very expensive.
And the other question is how fast is this can we reuse the index structures the optimizations that people have built over the last 25 30 years can we actually reuse these index structures using.
These impact scores that kind of looks similar to terms statistics does that work.
Yeah, let's look at this there's was a paper from 2021 from Joel McKenzie and a bunch of colleagues and they looked at this question and they looked at this from the perspective okay what are the distributions like the distributions of the different vectors for different types of models.
So if we look at the m25 the unique terms and this is for the msmarkle passage corpus.
There's 2.6 to 0.7 million unique terms that were created in the index if you use bm25 around 30 terms per document five terms per query and you have very very fast search through using this for example the piece engine.
And they try different types of models encoding this corpus to see how this statistics change and how the latency changes.
And for example deep impact one type of model it has a lot larger vocabulary it adds or has a lot more unique terms it has a lot more terms per document and a lot fewer or a bit fewer terms per query.
Unicoil on the contrast has a very very small vocabulary compared to bm25.
It's constrained to the vocabulary of the subword token vocabulary of the baseline model and it again has a lot more terms per document and a few more terms per query.
And another model displayed same as unicoil constrained to the vocabulary of the base model and it adds a lot of terms to the document and to the query.
And this reflects itself in the latency of using just a plain inverted index the piece engine it is a lot slower using these impact weights actually makes things way way slower.
Even though we are a bit more effective, but how can we maybe get to a stage where we're still as fast as using the term impact scores and get the efficiency in retrieval using these learned impact scores.
And okay the conclusion no we can't reuse these these index or in yeah these engines that were developed because the optimizations that were developed for these term frequency distributions just don't work very well for these neural sparse models.
So what maybe two strategies we can work on and this is the last part for me before Antonio takes it away I want to give a bit of context what kind of stuff we can do.
Two different strategies we could follow on the one hand the one is early exiting where we just don't score everything we try to see okay try to only compute the scores for the documents that maybe.
We actually need to compute the scores for and one way to do that is for example here on the left side for every single document we have a very quick way to estimate an upper bound score this is the score that the document.
Could achieve for a certain query and we do this very very quickly.
And then if we want to for example in this case get the top three documents we can score the documents one by one the first one we have an actual score of 9.5 for example the second one a bit lower than the actual score as well and stuff like that.
Now we have the top three scores and then we know the fourth and fifth document their maximum potential score is lower than the current minimum score of our top three documents are so we don't actually need to score these we can just skip scoring them and save a lot of computation in that way so we don't actually score these and be done with that.
Or the other strategy is we score everything but approximately we use some faster scoring mechanism yeah to score everything but not as accurately.
And this is yeah has a couple of advantages for example you're very very fast so in this case these are the actual scores and we might approximate these scores and compute them way way quicker the problem here is we don't have exact scoring anymore.
For example in this case we have one document that has a score the exact score should be 4.8 this one should be 6.2 but our approximate score is actually switched the order of the documents so you're not actually sure you're getting the exact top k so we have the trade off here but we'll probably get a lot quicker.
So these two strategies we can follow or in general that's how I would frame it or the potential we can save and that's where Antonio jumps in and talks about BMP.
Yeah so following the two approaches that 30 just described we thought we thought about sort of like coming up with a completely different approach that is not actually based on inverted indexes or at least not the way we are used to.
Well first of all we laughed the mental model of having every document going to be indexed in inverted index into passing lists and we started thinking about vectors which is a very common pattern in dense retrieval to have dense vectors vectors such as yeah a concatenation of like floating point values.
But those are different those are different because those are like sparse vectors what does that mean it means that for not all the positions in these vectors are actually positive values or actually non zero values.
For as for a sparse model for a lexical model as part factor indicate is basically indicating which tokens out of the original lexicon or the original vocabulary so all the unique terms that you see in the corpus which tokens which.
terms are actually present so as you can see for example I love New York contains only three terms and only three positions in the sparse vector that corresponds are actually set with a value and those values are actually.
and generated using a sparse model in this get learned sparse model in this specific case so now instead of having posting list we have vectors and without a bit about how can we make this more similar to the standard vector retrieval process that we see in vector databases and and the idea is to basically have.
the collection of documents as as as vectors represented as a concatenation of these vectors but like also split into basically blocks as you can see here we have like three blocks each block contains three vectors.
So now when you receive a query you also produce a sparse vector you convert it into a sparse vector by setting the position of the query terms for which that is contained in the original query text and you could potentially like compute the score for every document in the collection by you know doing a dot product a simple dot product between the query vector and the document vector.
Now if you do that you're not saving any time because you're essentially scanning the entire collection the entire representation.
So the idea was okay let's actually create some upper bounds so some scores that will tell us if we actually need to enter the block and score exhaustively the entire block or not.
So we did what we added essentially an additional interaction an additional data structure of vector of maxis which are essentially the max for every position in the block contained.
So for every position we look at the max score for all the in this case three vectors for that block and we represented as a single vector of max course.
Now if your block is big enough let's say contains eight vectors 16 32 64 and so on you're basically reducing the number of vectors for which you have to compute the dot product by factor of the block size.
Literally making a query processing x times faster with respect to what the block size is.
And so now running dot product against the vector of maxis.
Well first it's a very fast operation because it's on fewer vectors and at the same time it gives you like an upper bound so a good estimation of what's going to be inside the each block.
You end up having this essentially priority list and you can use this priority list to basically jump around.
Between blocks and say yeah I'm going to score this but I'm not going to score the other one which goes back to the early termination approach that fairly was mentioning.
In order to do that and decide what you're not going to score you maintain like a top k e which is you know a data structure that.
It keeps essentially the top k elements most valuable for your retrieval I estimate score and you always compare with the lowest.
At least important element so usually the one that has the lowest score.
Simple and faster we also introduce point quantization so instead of having a sparse vector of floating point values we decided to use 8 bits for every element.
So the standard linear quantization which makes things much faster because you can then.
And this was also useful for another reason that I'm going to introduce very soon.
Which is sorting now we mentioned we have a list of like a priority list so a list of upper bounds scores.
Upper bound scores that will tell you like which is the most promising block to access first.
You want access in decreasing order so you literally want to sort this this this course.
The problem is that you know if you're operating at the millions scale even sorting millions of values can be very expensive and slow.
So the standard traditional sorting even done in place and so on it's like still to slow.
We thought about like using a bucket for for and and this was possible for one reason you have a predefined set of buckets.
I mean in this example it's 256 predefined set of buckets if you quantize to 8 bits and you know that you're going to summing up up to a max of number of terms.
You know that you know these array of buckets can basically increase to a power of 2 to the 16 or something manageable essentially.
What the way it works it's actually very simple so you iterate the upper bounds and you place them in the position corresponding to a score to the score those are are essentially.
You know quantized score so you know exactly which is the array index that you have to access and each array is literally like a list of elements so you can append at the end.
Now the returning these bucket IDs in order it basically means iterating on the bucket sort.
Oh sorry on the on the on the bucket array.
And and you know materializing the final the final sort.
This is much faster for this specific use case than then traditional sorting and yeah it's basically it has some real world advantages like you know no cash misses.
No no the branch miss prediction and and allocation free and practically you know you can keep the bucket array fixed and you only have to clear it out so you know not really allocating it every every time.
There is another important concept which is we are dividing our vectors into blocks.
The the way you assign a vector as part of vectoring to a block will make a difference in in the speed of your algorithm and the reason is if the if you try to maximize all the similar documents in a way into one block you know the decimilar documents are probably going to answer like.
And so clustering these documents will make a difference in terms of like what how many live areas how many live blocks you have in in your collection.
So that basically means clustering in this case trying to maximize sparsity of the max of the vector of maxes.
Which in in the end and simple world basically means cluster together documents that have common terms.
So that table sorry that plot shows essentially like what's the difference between random assignment of of sparsity vectors and curated assignment which is.
Document reordering technique so in approach where you try to reorder documents that are similar.
That can be replaced for example with camines or other similar similar approaches so by doing that you're trying to to squeeze together.
The similar sparsity vectors that will probably end up in the in the same search result.
So comparing to the by the baseline we we saw like the early techniques the early termination techniques that are definitely like popular these days and.
And you know present many search engines like max core and B and W don't work extremely well with the learned spars models and what we noticed was reduction in in latency.
It was quite sensible.
So I'll pass it to 30 for.
The rest of the talk.
Yeah, thank you.
So I'm going to quickly just show a bit like how can you maybe use this yourself and also come a bit to the why rust is in this title of the talk as well.
So yeah, how do you how do you want to use this.
BMP it's on on GitHub I think do we have a QR code for that for BMP I think at the very end it's it's late for sure you can find it.
So there's a rust and a python interface here in this example is how you can use it in python either you can use batch inference and you just give it index and some queries.
And get the top k and whatever or you can create your search or give it an index and then search through a query by query.
Yeah, batch and single query interface and how do you or the question is now in this case how do you get this index how do you create the the BMP index.
And the answer to that is a sift if you haven't heard of sift before.
If is the common index file format here just like a quick example kind of it just defines it's trying to be an interface between different types of indexes and it's trying to define a unified format where okay we have some postings and some postings list and we just save everything.
Unified format for everything and then yeah was defined in this initiative and there's a couple of different tools that you can convert between the different formats so for example.
Between the the piece of research engine and sift you can convert back and forth and there's also converter from Jason L files of just yeah dictionary is pretty much and convert that to sift and then there's also one tool that you can go from sift to BMP and that's if you want to try it out yourself probably the easiest ways to have a Jason L convert that to sift convert that to to a BMP index.
Yeah, this was from from a paper a cigar our 2020 from from Jimmy Lynn feel free to give it a read and yeah how does that work there's a tool sift to BMP you just give it the sift index file and then it outputs a BMP index.
How might you without having to create your own sift index use this there's actually the sift hub that hosts a couple of different indexes already if you're doing research and for something.
There's for example the msmark of passage index already there you can just download it yeah repository of different sift indexes and queries for several popular.
Sparse models and things like that you can quickly download it and and run it and yeah if you have some further reading.
If you if you're interested I'll leave this up here for a quick second of anyone wants to take a picture otherwise we have two minutes I guess maybe.
Perfect the maybe I'll just show us a bit of a short like code demo that this actually works and yeah quick quick demo I guess so.
Where I need to find the correct via code window obviously there it is.
Let me zoom in a bit and.
Close all these and go like this okay so this is just a quick example script.
Some curl commands to download the sift index from the sift hub it's posted on on hugging face and open and yeah next command just converts the index to calls the sift to BMP converts the index to BMP index and the last one is just an example script which uses the BMP cargo.
Interface or BMP rust interface to run the query and then the end we use track evel to this runs the 2019 track deep learning queries and yeah I ran this a couple of minutes ago and we can show this pretty much run through grabs the whole collection converts it to BMP and in the end we have.
Yeah 24 seconds on my small laptop running on its battery to turn through these 44 43 queries and we actually get some results in the end so yeah works you can use it at home if you're doing research or something it's it's always a good bet at baseline feel free to use it thank you.
And if there's the now it's gone there was a Indian the talk will be in pre talks and you can read it yourself the video is going to be recorded and should be a little by the end of next week.
I'm going to take questions and here you go and repeat the question please for the video.
Okay so the repeat or to repeat the question the question is and talk back to me if I misinterpret it but why here deep impact has such a different distribution of terms compared to the other sparse ones.
I think probably Antonio can hop in later as well but the optimizations that are built most of them.
You use early exiting and in this case because or it's built especially on having a very big vocabulary we have very very sparse vectors and then you can estimate the max scores really well because pretty much everything is sparse and then you have very good estimations for a particular document because a lot of it is sparse.
In this case for especially for unicole and splaid you're losing a lot of the sparsity or the yeah because you have compared to about 3 million now you have only 30,000 different dimensions and but still you have in this case 230 of these are non zero so.
So especially you have higher max scores per document that you're estimating and then it's very difficult to find good early exits is how I would intuitively put it so that makes sense.
You're almost going to and you're not you're not probably not doing a linear scan but you need to score a lot more yeah.
I question by you when you know that there's a.
Yeah repeat the question let me tell me if I understood this correctly you're basically asking what happens when you have terms that.
Similar spelling or.
Yeah people choose words to choose that word they don't want to choose the synonyms or words that are in contact typically used.
Yeah that's right and if you remove that and you use this sort of sparse vectorization you reduce you have.
Oh no the lexicon is still present right so you still have the original term.
The only thing is that you're not repeating it in the representation you know you just create one array once.
You don't need the lexicon or you're basically converting like term into an idea right.
I think we can I have to take it offline if you want to chat more about like how it works the internal some.
Yeah but we keep the terms we don't lose I mean they're part of the.
Okay.
Thank you very much.