The unreasonable effectiveness of BM25 for agentic search — Jo Kristian Bergum, Hornet.dev
AAI Engineer
Computing/SoftwareInternet Technology
Transcript
00:00:00So great being here. I'm Joe Burgum. I'm the CEO of Hornet Dev, and I'm here today to talk about
00:00:19the unreasonable effectiveness of BM25 for Argentic Search. So how many of you heard about
00:00:24BM25 before? Is it new or is it? Oh, quite a few, so that's great. I'm also watching the World Cup.
00:00:32Norway is playing there against Ivory Coast's second half. Norway is leading, so that's good.
00:00:37So, yeah. And at Hornet, we are building retrieval infrastructure for agents, and I've been working
00:00:46on search and retrieval problems for a long time. As you can tell, I'm gray-haired. I've been working
00:00:52in this space for more than 20 years, and in the talk today, I'll talk about why this kind
00:00:59of 30-year-old lexical scoring function is making a strong comeback. First, I will talk a little bit
00:01:08about what I mean by Argentic Search or Argentic Attribal and kind of define that for you, all of
00:01:14you. My definition is that Argentic Search is essentially searched inside agent loop. So you
00:01:22have an agent that is trying to accomplish a task, write the coding or do some deep research
00:01:28or whatever task, and inside that you have some kind of information need for the agent, right,
00:01:34in order to get that task done successfully. And you essentially need three things to kind
00:01:41of build a good agent search system. And that is you need a capable model, a model that is
00:01:47able to use tools and is able to formulate queries. You also need a harness around the model and
00:01:55how you kind of expose the retrieval and the search functions to the model. There's different
00:02:01ways to do that. It could be through tool calling or it could be through code mode. Ido here demonstrated
00:02:08what I call code mode for exposing retrieval infrastructure. So that's the harness part.
00:02:14And you also need a retrieval engine to be able to do searches efficiently, potentially over a billion
00:02:23scaled document sets. And to define BM25, so BM25 actually stands for best match 25. So there
00:02:33were some researchers doing plenty of different experiments and experiment number 25
00:02:38turns out to be the best one. So that's the background of the name. It's essentially a scoring function.
00:02:44So you can imagine you have a query and you have a document and you calculate some kind of score
00:02:50by interaction between the query terms and the document terms, and you come up with a score,
00:02:55and you hope that this score kind of is a good proxy for the relevancy of the document with regards
00:03:01to the query. Right. So one way to calculate BM25 would be to take all the documents and score each
00:03:08each of them, you know, and then figure out what are the top K documents. And then there's like 30 or 40 years
00:03:14of interest in how you accelerate that type of retrieval, top K, lots of different algorithms. We also invest a lot in that.
00:03:22I'll show something in this direction, but BM25 is the scoring function and there is a way to kind of accelerate top K retrieval.
00:03:30BM25 hasn't changed. It's the same scoring function, but the change here is really that we got a more powerful user.
00:03:38Edo talked about general knowledge. The LLMs today have a lot of general knowledge. They know about entities, they know about companies, they know about dates, they know a lot.
00:03:50And by using that kind of implicit knowledge that is built into the parametric model, they essentially become very good at search.
00:04:01And that's the really change here now that we're kind of making BM25 more relevant.
00:04:09And BM25 used to be a kind of a baseline function. Any information retrieval research would include a BM25 baseline,
00:04:17and then you would put something fancy advanced neural, fancy stuff, and then you would compare it with BM25.
00:04:24And I also think it's interesting in how we evaluate search before, because you will simply look at 10 blue links and you like how scan it and you compute some metrics.
00:04:34A lot of that is now going away because the agent is not really, it's kind of powerful in the way that it can type out a lot more queries than a human can do.
00:04:45So it's less relevant to think about evaluating these systems just by a single shot query.
00:04:53And this is one of my kind of favorite benchmarks out there. I like to talk about benchmarks.
00:04:59So BrowseCom Plus is a deep research benchmark published in a paper last year, and it has almost or exactly 830 questions.
00:05:13These are riddle-like. Think about it like a pub quiz. Do you have pub quizzes in the U.S.?
00:05:19Yeah, okay, great. So like kind of a riddle type of questions, quite long.
00:05:23And the agent, the harness of this kind of, or the protocol of this benchmark is that you have a model,
00:05:31and it gets a very simple tool called search, and it accepts a query string, and you return some snippets back to the model.
00:05:40And the corpus is about 105,000 or 100,000 documents, so that's kind of tiny, and these are web documents.
00:05:47And the end-to-end accuracy, all of these questions have a golden reference answer, and you can kind of check if the model and the entire loop produces that exact answer.
00:06:02But why do we need retribble? I like to compare context windows with floppy disks, because I'm old in the 80s, right?
00:06:11We installed these kind of games on our computers using floppy disks.
00:06:15So one kind of, you guys are so young, so you don't probably have this kind of nostalgia, but one floppy disk could fit about 1.4 megabytes of data.
00:06:26And the current models, before they start degrading in quality, that's, in my opinion, around 350,000 tokens.
00:06:34So that's one floppy disk of data, right?
00:06:38So you need retrieval in order to fetch the information that you actually need to put into the context window.
00:06:47And BrowseCon+ really demonstrates how retrieval quality affects the end-to-end accuracy of the task, right?
00:06:57The end-to-end accuracy here is essentially, is the model equipped with this search tool able to answer the question, right?
00:07:05The riddle-like question.
00:07:07And if you artificially just stuff the evidence documents that is needed to answer this question
00:07:16into the context window of the model, the accuracy is really high, right?
00:07:21So reasoning is not the bottleneck.
00:07:23The model, given the evidence up front, answers the question with a very high accuracy rate, even GPT-4.
00:07:33But if you expose the model with the harness with a retrieval tool, that accuracy falls,
00:07:39because it now depends on the harness, it depends on the model's ability to formulate queries,
00:07:44and the retrieval quality of the retriever.
00:07:49So for me, this is also quite important because even if we get perfect models, like models that are kind of AGI,
00:07:57you don't have to append, make no mistakes.
00:08:00You still will be limited to a context window that is approximately a floppy disk, right?
00:08:04So you have to decide what goes into that context window.
00:08:07And I think retrieval is still very relevant, as the previous slide showed.
00:08:13And in this Browse Comp Plus dataset, one of these riddle-like questions becomes a search trajectory.
00:08:20Because the model executes the query, gets some response back, reads it, reformulates the query,
00:08:27and continues until it has kind of filled up the context window, or found the answer, whatever comes first.
00:08:36And we spent some time to investigate these trajectories.
00:08:44To see how GPT-5 is formulating queries.
00:08:49And we found a lot of interesting aspects with that.
00:08:52We described it in a recent blog post as well.
00:08:55You can find it on hornet.deb.
00:08:57And we like to compare it with an AOL query log.
00:09:02So AOL was like a service, back in the day, had some search interface.
00:09:08And they accidentally published a very large sample of what people were searching for on the web.
00:09:17And they were quite short.
00:09:19And I have seen more recent query logs as well.
00:09:22And the user human pattern are still searching with just a few terms.
00:09:27GPT-5, on the other hand, it's a much more powerful user.
00:09:31It has the general knowledge.
00:09:32And it can like, bam, write out very long queries.
00:09:35It can use a lot of syntax operators that are kind of useful from...
00:09:40It has learned from web search, or site operator, phrases, etc.
00:09:45And this is a new type of workload.
00:09:52And on BN25, BN25 has essentially two hyperparameters
00:09:57that controls various aspects of the scoring function.
00:10:01And I talked about having a baseline.
00:10:04And BN25 was usually a baseline.
00:10:06And Browser Comp Plus as well has a baseline with BN25.
00:10:10But it turns out that that baseline is terrible.
00:10:14So when you look at fancier techniques, embedding models, what have you,
00:10:20it stands out as a much better retrieval paradigm than BN25, if you look at the original paper.
00:10:26But more recent research shows that the parameters that were used in the Browser Comp Plus
00:10:33research paper was not really adequate to handle these kind of long documents.
00:10:37So I like this, which BN25 do you mean?
00:10:40Because it has a quite dramatic impact on that specific benchmarks on the overall accuracy.
00:10:50And why is BN25 now more powerful with the new user?
00:10:56So I mentioned the general knowledge of the user and that he can type faster
00:11:00and be more specific as a more powerful user.
00:11:02And exact matching is still relevant, right?
00:11:06Because the model knows names, entities, zip codes, SKUs, what have you.
00:11:12That is not so easy to represent with an embedding model, which kind of encodes
00:11:17all the tokens into a fixed vocabulary.
00:11:21It's also relatively cheap, especially if you take into consideration the cost of doing embedding
00:11:27inference, right? Some of these embedding models have like 8 billion parameters and you encode text
00:11:32and you have to stand up infrastructure for this and what have you.
00:11:36So it's quite simple and also the tooling in the overall ecosystem is quite good.
00:11:43So it's readily available.
00:11:45And it's also very easy for the model to inspect the results and understand why a certain query
00:11:51formulation returned the result it did, right?
00:11:54Because you're matching literal terms and phrases and things like that,
00:11:58which can help it kind of reformulate the queries.
00:12:03So these are the three key things.
00:12:06And now into more hot topics on like what is all you need.
00:12:11And this is a very recent research that came out from Waterloo, from Jimmy Lin's group up there.
00:12:17They are doing a great job at the information retrieval research and also on agentic search.
00:12:23They have a recent paper that I love.
00:12:26It's called Scaling Direct Corpus Interaction via Dynamic Workspace Expansion.
00:12:32So I'll spend some time on expanding this.
00:12:34So imagine you want to stand up web search infrastructure for agents.
00:12:39A lot of companies are doing that at the moment.
00:12:41We are also working with some of these companies to help them build infrastructure for powering that
00:12:47kind of use case.
00:12:48And there you have potentially billions of documents, right?
00:12:53So that doesn't fit into the context window.
00:12:55So you obviously need retrieval.
00:12:57And BM25 is a good baseline.
00:12:59So you can retrieve information over that.
00:13:03And the results of this is you can imagine this as a search engine result page, SERP, for agents.
00:13:15Because you can place these documents that are retrieved from the retriever into a workspace.
00:13:20And if you organize this workspace as a file system, you can play into the same things that you have around skills.
00:13:29You can have progressive disclosure because you can have the document, like the title of the document,
00:13:35and a small snippet of the document, and expose that to the model.
00:13:39And the model can then also decide, oh, I need to read more of the document.
00:13:43And when it's doing that, it can use all the primitive tools that it's really good at using.
00:13:48You all use coding agents.
00:13:49So you all see in grep and rip grep and sed and orc and whatever it's doing to kind of manage context.
00:13:55So here you get the benefits of both worlds.
00:13:58And also you get to combine sandbox infrastructure, retrieval infrastructure, and VFS and just bash and whatever.
00:14:05So it's also quite exciting, right?
00:14:06Because it combines all of these new type of paradigms that is happening at the moment.
00:14:11So I'm really excited about this type of direction.
00:14:14And it's also kind of a hack, right?
00:14:16To optimize for what the models are good at the moment, right?
00:14:19Because all the frontier LLM companies are optimizing their model for coding, for bash, for tool use.
00:14:27So if you put your kind of end-to-end task on the trajectory of that, you kind of, whatever,
00:14:31there's a new model, you know there's going to be better at this as well, right?
00:14:37So it might be that when we get AGI, they can just use the browser, we'll see.
00:14:41But currently this is a very powerful way to build retrieval infrastructure and a whole editing search experience.
00:14:53And when it comes to evaluation, right?
00:14:55I talked about this earlier as well.
00:14:57In traditional information retrieval, we were used to having just one query, one rank list, compute and DCG, and compare it.
00:15:07That is no longer very relevant when the new user is an agent, because that agent can reformulate queries,
00:15:12and do more queries, and do expansion, and do all kinds of different stuff, right?
00:15:17So a lot of the classical information retrieval evaluation is now kind of dead.
00:15:23Instead, look at, like, see if the model can perform the task it's set to, and for example,
00:15:30for question answering, does it get the answer right?
00:15:35And we at Hornet, we are betting on BM25 as one of the primitives, and we have set out on a vision
00:15:42to kind of have the best, most efficient way to evaluate BM25, because I think it's such a strong,
00:15:51fundamental, primitive, and this illustration compares some animized engines, comparing with Hornet,
00:15:59on the same type of hardware, with web documents, 100 million web documents, on a single node.
00:16:07And as you can see, Hornet has a much more efficient implementation than the other engines,
00:16:13and can do more throughput for the same type of bugs, which for a lot of companies that are building
00:16:19infrastructure at the moment for web search, et cetera, means a lot in savings.
00:16:24What is the y-axis?
00:16:26The y-axis is QPS, sorry.
00:16:32The y-axis is, oh, sorry, the y-axis is latency, I'm sorry.
00:16:40So, four claims to take away from this talk. There's a new user, it's more powerful, it's able to type faster, it's able to read faster, it's able to reformulate queries, and it has a lot of general knowledge, which makes simple tools like grep and BM25 more powerful.
00:17:03That's number one, that's number one. Number two, which BM25 do you mean?
00:17:07There are differences in implementation, in performance, in parameters, so think about that.
00:17:14And also, why is it effective for agentic search? It's simply because it's explainable for the model, so the model can see and also use it in combination with grep, right, because you have literal matches, and grep is almost about literal matches as well.
00:17:27And the combination of these two is a very strong agentic search or agentic retrieval paradigm.
00:17:39There's a lot of references, I think I will publish a talk, or the talk will be published, and also the slides.
00:17:47And if you hated it, you can tweet at me.
00:17:55There is not, I was told that there is not a room for questions, but happy to chat about retrieval, you will find me around the conference, probably the best way to reach me is through my X account.
00:18:08And that's it.
00:18:25We'll see you next time.
Community Posts
No posts yet. Be the first to write about this video!
Write about this video