Sign in to continue learning
Retrieval Augmented Generation (RAG)
Intermediate
24 hours 33 mins
Topics
Data Processing
Document Processing
RAG
While TF-IDF remains a classic keyword search algorithm, the algorithm used in most retrievers is called Best Matching 25, or more simply BM25. It's called this because it was the 25th variant in a series of scoring functions proposed by its creators. It makes a few improvements upon TF-IDF, so let's explore how those work. Here's the formula for BM25. It actually works very similarly to TF-IDF, with a few key additions you'll see momentarily. This formula generates a relevant score for a single keyword for a particular document. Summing these scores up across all keywords generates a total relevant score for a single document, which can then be used for ranking. Let's now see how BM25 improves on TF-IDF. First, documents score diminishing returns as they include more instances of a keyword. The idea here is that a document that includes the keyword pizza 20 times isn't actually twice as relevant as one that includes pizza 10 times. This behavior of discounting additional instances of a keyword is referred to as term frequency saturation. Second, longer documents are still penalized as they are in TF-IDF, but in BM25 these penalties are also diminishing. While penalizing long documents is important, TF-IDF can do so too aggressively in a way that overly discounts longer documents. BM25 applies diminishing additional penalties as documents grow in length. The result is that long documents still score highly as long as they have a fairly high frequency of the keywords. This process of adjusting scores based on document length is called document length normalization. BM25 also differs from TF-IDF in that it includes two tunable hyperparameters. These allow you to control the degree of term frequency saturation and document length normalization, or in other words, how rapidly documents stop being rewarded for repeated keywords and penalized for increased length. In a production retriever, you would tune these hyperparameters in order to land on an overall scoring system that best fits the data in your knowledge base. In a production retriever, the standard keyword search algorithm is BM25. It tends to perform significantly better than TF-IDF at finding relevant documents, is roughly equivalent in terms of the computational resources it requires, and the ability to tune its hyperparameters to your dataset makes it much more flexible. Let's briefly review keyword search and talk about how its strengths are used inside of a typical retriever pipeline. The core idea of keyword search is that you match documents to prompt based on how frequently keywords from the prompt appear in each document. As a part of this process, both prompts and documents are converted to sparse vectors that count how often each word in the system's vocabulary appears in that piece of text. TF-IDF or BM25 are just different approaches for processing these sparse vectors in order to score and then rank documents. These methods also account for important factors like the rarity of a keyword, how often a document contains a keyword, and document length. BM25 is the most commonly used keyword search algorithm that has withstood the test of time for decades since its invention. It strikes a good balance between complexity and performance in real-world applications. The primary strength of keyword search is its simplicity. It's a relatively straightforward approach that works well in practice, often capable of performing quite well on its own and frequently setting a competitive benchmark that more advanced techniques may struggle to surpass. It also ensures that retrieved documents will contain the keywords from your user's prompt. Especially in situations when you expect users to use technical terminology or exact product names, this kind of exact keyword matching is particularly important. Despite all its strengths, keyword search does have weaknesses. It ultimately depends on the query containing keywords that exactly match the words in the document. If a user sends a prompt that has a similar meaning to a document but just doesn't include the right words, keyword search won't be able to find that match. So let's have a look at semantic search and how it addresses this problem.
