Relevant results despite typos: combining BM25 and fuzzy matching
Many search features rely on substring matching, such as LIKE '%query%' or strings.Contains. This only finds the exact sequence of characters: setings won't match "Open user settings", and export pdf won't match "Export the current document as a PDF file".
Better search has to solve two problems: relevance and typo tolerance. BM25 ranks results by how relevant their words are to the query, and fuzzy matching recovers misspelled words. Queries that use different words for the same idea need synonyms or semantic search, which are outside the scope of this post.
This post explains how the two techniques complement each other, using a small example and the implementation decisions that most affect the results. It also shows how the same search can select the tools of an AI agent.
The example searches a set of text editor commands. Each command has an internal name and a short description, and the search covers both. The commands referenced in this post are:
ID | Internal name | Description |
|---|---|---|
A | file.exportPDF | Export the current document as a PDF file |
B | file.exportMarkdown | Export the current document to Markdown |
C | view.colorTheme | Pick a color theme for the editor |
D | settings.open | Open user settings |
E | settings.keyboardShortcuts | Edit keyboard shortcuts |
F | file.openFile | Open a file from disk |
G | view.zoomIn | Make the text bigger |
What is BM25?
BM25 (Best Matching 25) is a ranking function. Given a query and a collection of documents, it assigns each document a score that reflects its relevance to the query. In the example, each command is a document. BM25 was developed in the 1990s and is still the default ranking function in Lucene and Elasticsearch.
BM25 does not compare raw text. It first turns both the commands and the query into terms: simplified words that are easier to compare. This step is called tokenization. In the example, it:
converts everything to lowercase,
splits internal names such as
exportPDFinto "export" and "pdf",removes common words such as "the" or "to",
removes endings such as "-ing" or "-s", so "exporting", "exports" and "export" all become "export".
The description of B, "Export the current document to Markdown", becomes the terms "export", "current", "document" and "markdown".
The BM25 formula is based on three principles:
a. Rare terms carry more weight. A term that appears in many commands, such as "file", says little about relevance. A term that appears in only one, such as "pdf" in A, is a strong signal. This component is the inverse document frequency (IDF).
b. Repetition has diminishing returns. A document that contains a term five times is more relevant than one that contains it once, but not five times more. The parameter k1, commonly set to 1.2, controls how quickly this effect saturates.
c. Document length is normalized. Longer texts contain more terms and would otherwise match more often. The parameter b, commonly set to 0.75, controls the strength of this normalization.
For each term of the query, BM25 computes one value per principle:
rarity = ln(1 + (N − n + 0.5) / (n + 0.5))
length = 1 − b + b × (document length / average document length)
frequency = f × (k1 + 1) / (f + k1 × length)
term score = rarity × frequencyN is the number of documents, n is the number of documents that contain the term, and f is the number of times the term appears in the document. The score of a document is the sum of the term scores of all the query terms. A term that does not appear in the document has f = 0, so it adds nothing.
What is fuzzy matching?
BM25 only finds terms that appear in the commands. A misspelled word such as setings appears in none of them, so if every word of the query is misspelled, BM25 finds nothing. Fuzzy matching handles this case: it looks for words that are almost the same as the query.
A common way to measure how close two words are is the Levenshtein distance: the smallest number of single letter changes (adding, removing or replacing a letter) needed to turn one word into the other. setings needs one added "t" to become "settings", so the distance is 1.
One wrong letter matters more in a short word than in a long one. For that reason, the distance is turned into a similarity between 0 and 1, where 1 means identical:
similarity = 1 - distance / length of the longer wordFor setings and "settings", the similarity is 1 − 1/8 = 0.875. The example accepts a command when the similarity is at least 0.75. If the query has several words, it finds the closest word in the command for each of them, and the average of those similarities must reach 0.75.
Why combine them?
Each technique solves a case the other cannot. The table compares substring search, BM25 and fuzzy matching on four queries:
Query | Should find | Substring | BM25 | Fuzzy |
|---|---|---|---|---|
export pdf | A | the two words are not next to each other | A | Not used: BM25 already found it |
exporting | A, B | the text says export, not exporting | A, B: exporting becomes export | Not used: BM25 already found it |
theme color | C | the words are in the other order | C: word order does not matter | Not used: BM25 already found it |
setings | D | typo | :cross_mark: no command contains setings | D, E: close enough to settings |
The two are combined with one rule: BM25 runs first, and fuzzy matching runs only if BM25 finds nothing. Fuzzy matching also accepts words that are only similar to the query, so it returns some wrong matches. If it ran on every query, those wrong matches would mix with the good BM25 results.
The rule has a cost. For open setings, BM25 finds the commands that contain "open", such as D and F, so fuzzy matching never runs and the typo is not corrected.
Decisions that affect the results
Weight names over descriptions. A match in the internal name is a stronger signal than a match in the description. We count each term in the internal name twice.
Use a relative threshold, not a fixed top N. A fixed number of results includes weak matches when there is one clear winner and cuts off good ones when there are many. We keep only results that score at least 50% of the best score, with an absolute minimum of 0.05, and then normalize scores so that the best result is 1.00.
Cap the number of results. A query that matches almost everything does not help the user. We return at most 40% of the commands, rounded up. In the code below, this share is the constant
maxShare.Watch for floating-point errors. We calculate the cap with
ceil, and the product can be slightly off:0.07 * 100evaluates to7.000000000000001, soceilreturns 8 instead of 7. We subtract a small epsilon (1e-9) before rounding to avoid this.Break ties deterministically. Results with the same score can otherwise come back in a different order on each run, which makes tests unstable. We sort by score and then by internal name, which keeps the order fixed.
Implementation
We wrote the example as a small Go program that uses only the standard library. The main search function applies the fallback rule, the tie-breaking and the cap:
func (idx *Index) Search(query string) []Result {
results := idx.bm25(query)
if len(results) == 0 {
results = idx.fuzzy(query) // only when BM25 finds nothing
}
// Deterministic order: score first, then name.
sort.SliceStable(results, func(i, j int) bool {
if results[i].Score != results[j].Score {
return results[i].Score > results[j].Score
}
return results[i].Command.Name < results[j].Command.Name
})
limit := int(math.Ceil(maxShare*float64(len(idx.docs)) - 1e-9))
if len(results) > limit {
results = results[:limit]
}
return results
}Results for three queries, with scores normalized so that the best result is 1.00:
Query | Results |
|---|---|
exporting | B (1.00), A (0.96) |
export pdf | A (1.00) |
setings | E (0.88), D (0.88) |
For exporting, A and B contain "export" in the same places: in the internal name and in the description. The difference is length. A's description ends with "as a PDF file", which is longer than B's "to Markdown". When two commands match the same terms, BM25 gives the shorter one a higher score (the third principle), so B ranks slightly above A. For export pdf, B also contains "export", but its score is below 50% of A's, so the relative threshold removes it. For setings, E appears because its internal name contains "settings". E and D have the same score, so they are ordered by internal name.
We use the same approach to select the tools of our AI agents. An agent receives the name and description of every available tool with each request, and the more tools it has, the longer the request becomes, which can make the model's choice less reliable.
A tool has the same shape as a command, so we index tools by name and description, use the user's request as the query and send only the selected tools to the model:
func selectTools(idx *Index, all []Command, request string) []Command {
results := idx.Search(request)
if len(results) == 0 {
return all // nothing matched: the model sees every tool
}
selected := make([]Command, len(results))
for i, r := range results {
selected[i] = r.Command
}
return selected
}To test it, we treat the editor commands as the tools of an agent:
Request | Selected tools |
|---|---|
export the document as pdf and markdown | A, B |
open the settings and pick a theme | C, D |
markdwon | B, through the fuzzy fallback |
do the same for the other one | none, so every tool is sent |
With an agent, some of the decisions above weigh differently:
A missing tool costs more than an extra one. Requests often need more than one tool, as in the first two examples. The model still decides which tools to call, so it can ignore an extra tool. A missing tool is worse: the agent cannot complete part of the task. This is why we keep every tool above the relative threshold instead of only the best one, while the cap keeps the selection small.
When nothing matches, send every tool. Follow-up messages such as do the same for the other one contain none of the terms that matter, so the search finds nothing. Sending no tools would leave the agent unable to act, so the model receives all of them: the request is longer, but the agent keeps working. Adding the previous message to the query is one way to handle these cases.
Descriptions are part of the index. The search can only find a tool through the words in its name and description. increase the font size selects nothing, because G is described as "Make the text bigger". With "font" in the description, G is selected. Descriptions written with the words users use improve the selection, and the model reads the same descriptions to choose which tool to call.
Conclusion
BM25 and fuzzy matching work well for small and medium collections such as commands, settings, products or documentation pages. Both run in memory, need no external services and return deterministic results, which makes them easy to test.
However, there are some limitations:
No semantic understanding. A search for
enlargedoes not find G ("Make the text bigger"), because they share no terms. Synonyms and intent require semantic search with embeddings, which can be combined with BM25 in a hybrid search.Limited scalability. The fuzzy fallback compares the query against every word in every command. This is fine for small collections but slows down as the collection grows.
Parameter tuning. Values such as the 50% cutoff or the 0.75 similarity threshold depend on the data and should be checked against real user queries.
For larger collections, engines such as Postgres full-text search, Meilisearch and Elasticsearch provide relevance ranking, and some also provide typo tolerance. Knowing how BM25 and fuzzy matching work makes it easier to configure these engines and to understand why they order results the way they do.
