12.6.4 — Keyword and Hybrid Search

Two weeks after Cartwise switched product search to embeddings, the complaints changed. "Sneakers for jogging" now worked beautifully. But a customer who typed "a54 charger", meaning a charger for the Samsung Galaxy A54 phone, got a page of chargers for every phone except the A54. Another typed the exact model code from a box, "SM-A546E", and got phones that were similar in a general way but not the one with that code.

This is the mirror image of the problem in 12.6.1. Embeddings capture meaning and deliberately blur the exact surface of the text: that is what lets "sneakers" match "shoes". But a model number, a size, a part code or a rare brand name has no meaning to blur. Its whole value is its exact spelling, and an embedding model that has rarely seen "A546E" places it somewhere vaguely phone-like. Old-fashioned keyword search, which matches exact words, is strong exactly where embeddings are weak, and weak where they are strong.

So real search systems use both. This page explains how keyword search works and ranks results, how it copes with typos, and how to combine it with vector search into hybrid search, which is the default for any serious product search or document retrieval system, including the retrieval inside RAG in Chapter 12.9.

1. Keyword search: the inverted index

Keyword search starts with a structure built ahead of time: for every word in the catalogue, a list of the products that contain it. Looking up "charger" gives you its list instantly, without reading a single product description. This is the same inverted index idea as in IVF from 12.6.3: "inverted" because instead of each product listing its words, each word lists its products. Every search engine has one at its heart, and Chapter 7.7 describes how search engines build and store them.

For a query of several words, the engine fetches each word's list and scores every product that appears in any of them. The question is how to score them, and the answer used almost everywhere is a formula called BM25.

2. BM25: how keyword matches are ranked

BM25 grew out of the TF-IDF idea from 12.3.5: a word counts more if it appears often in this product, and much more if it is rare across the catalogue. The name means "Best Matching, attempt number 25": it came out of a long series of ranking experiments by Stephen Robertson, Karen Spärck Jones and colleagues at City University London in the 1980s and 1990s, and the 25th variant is the one that stuck. It fixes two weaknesses of plain TF-IDF. Here is the formula, followed by what each part does:

\text{BM25}(D, Q) = \sum_{t \in Q} \text{IDF}(t) \cdot \frac{f(t, D)\,(k_1 + 1)}{f(t, D) + k_1\left(1 - b + b \cdot \frac{|D|}{\text{avgdl}}\right)}

Read it as: for each query word t, multiply how rare it is, \text{IDF}(t), by a measure of how often it appears in the product D, adjusted for the product's length; add these up over the query's words. The symbols: f(t, D) is how many times word t appears in product D; |D| is the product text's length in words; \text{avgdl} is the average length across all products; k_1 (usually 1.2) and b (usually 0.75) are tuning settings. The rarity part is \text{IDF}(t) = \ln\left(1 + \frac{N - n + 0.5}{n + 0.5}\right), where N is the number of products and n is how many contain the word.

Fix one: repetition stops paying. In plain TF-IDF, a word appearing ten times scores ten times more than once, so a seller who writes "charger charger charger" in a title climbs the rankings. In BM25 the count f appears on both the top and the bottom of the fraction, so the score rises quickly for the first mention and then flattens out, approaching k_1 + 1 however many times the word repeats. This is called saturation. The second mention adds a little; the tenth adds almost nothing.

Fix two: long texts do not win by being long. A 300-word description mentions "charger" more often than a 5-word title just because it is longer. The term with b divides by a factor that grows with the product's length relative to the average, so a word appearing once in a short title counts for more than once in a long essay. Setting b = 0 turns this off; b = 1 applies it fully.

Worked: "a54 charger"

Four products, N = 4, with an average length of 4.75 words:

Product	Text	Length
d1	samsung galaxy a54 25w charger	5
d2	iphone 15 20w charger	4
d3	galaxy a54 back cover	4
d4	fast charger cable usb c charger	6

"a54" appears in 2 of the 4 products, so its rarity is \ln\left(1 + \frac{4 - 2 + 0.5}{2 + 0.5}\right) = \ln 2 \approx 0.693. "charger" appears in 3 of the 4, so it is less informative: \ln\left(1 + \frac{1.5}{3.5}\right) \approx 0.357. Running every product through the formula with k_1 = 1.2 and b = 0.75:

Product	"a54" part	"charger" part	BM25 total	Rank
d1 (A54 charger)	0.679	0.349	1.028	1
d3 (A54 back cover)	0.741	0	0.741	2
d4 (charger cable)	0	0.457	0.457	3
d2 (iPhone charger)	0	0.381	0.381	4

Three things are visible. The exact match d1 wins, because it contains both words, and the rare "a54" carries twice the weight of the common "charger". Product d4 says "charger" twice but scores only 0.457 against d2's 0.381 for saying it once: saturation at work. And keyword search ranks the A54 back cover second, above every charger, because it matches the rarer word, even though a customer asking for a charger almost certainly does not want a back cover. Keyword search knows which words appear, not what the customer means.

import math

docs = {"d1": "samsung galaxy a54 25w charger".split(),
        "d2": "iphone 15 20w charger".split(),
        "d3": "galaxy a54 back cover".split(),
        "d4": "fast charger cable usb c charger".split()}
N = len(docs)
avgdl = sum(len(d) for d in docs.values()) / N                   # (1) 4.75

def idf(term):
    n = sum(term in d for d in docs.values())
    return math.log(1 + (N - n + 0.5) / (n + 0.5))               # (2)

def bm25(query, doc, k1=1.2, b=0.75):
    score = 0.0
    for t in query:
        f = doc.count(t)
        norm = k1 * (1 - b + b * len(doc) / avgdl)               # (3) length adjustment
        score += idf(t) * f * (k1 + 1) / (f + norm)              # (4) saturating count
    return score

q = "a54 charger".split()
print({k: round(bm25(q, d), 3) for k, d in docs.items()})
# → {'d1': 1.028, 'd2': 0.381, 'd3': 0.741, 'd4': 0.457}

Line (1) computes the average product length. Line (2) is the rarity of a word. Line (3) is the length adjustment: bigger than k_1 for longer-than-average products, smaller for shorter ones. Line (4) combines rarity with the saturating count. In production you would not write this yourself: search engines such as Elasticsearch and OpenSearch, and PostgreSQL's full-text search, implement BM25 or close relatives, with the inverted index, word normalisation and everything else.

What keyword search needs before it can match

Exact matching is only useful if "Chargers", "charger" and "CHARGER" count as the same word. So text goes through analysis before indexing, and queries go through the same steps: lower-casing, splitting into words, and often reducing words to a root form (stemming, so "chargers" and "charging" both become "charg"). Search engines also let you add synonyms ("sneakers" = "trainers"), which patches some of what embeddings do naturally, but only for the pairs someone thought to write down.

3. Typos: fuzzy matching

Customers misspell constantly: "chager", "ketle", "samsng". An exact keyword index finds nothing for "chager", because no product contains that word. Two classic techniques let keyword search tolerate typos, and both come straight from the algorithms of Part 4.

Edit distance. The edit distance, or Levenshtein distance after the Soviet mathematician Vladimir Levenshtein who defined it in 1965, is the smallest number of single-letter insertions, deletions or substitutions that turn one word into another. "chager" to "charger" is 1 (insert an r); "ketle" to "kettle" is 1. It is computed with the dynamic programming of Chapter 4.24.9. Search engines offer fuzzy queries that match indexed words within an edit distance of 1 or 2, using clever automata rather than comparing against every word.

Character n-grams. Break every word into overlapping chunks of three letters: "charger" becomes "cha", "har", "arg", "rge", "ger". A misspelling shares most of its chunks with the right word: "chager" has "cha", "hag", "age", "ger", sharing "cha" and "ger". Indexing these chunks lets the engine find words that share many of them. PostgreSQL's pg_trgm extension does exactly this with trigrams.

How this differs from what embeddings do

This is a question worth getting straight, because it is a common source of confusion. Edit distance and n-grams measure how similar two spellings are. Embeddings measure how similar two meanings are. They disagree all the time:

Pair	Edit distance	Embedding similarity
"running shoes" vs "running sores"	2 (very close)	low: shoes and a medical complaint
"running shoes" vs "sneakers"	11 (very far)	high: same kind of product
"charger" vs "chager"	1	usually fairly high

The first two rows are why neither method alone is enough. Edit distance would happily "correct" a search for shoes into a search for sores. Embeddings know nothing of the sort happens, and match "sneakers" with "running shoes" despite completely different spellings. The third row shows an overlap: embedding models split rare or misspelled words into smaller subword pieces (explained in 12.7.2), so "chager" shares pieces with "charger" and often lands near it, giving embeddings some typo tolerance for free. That is also how an LLM copes with a typo in your prompt: not by computing edit distance, but because the pieces of the misspelled word, in context, still point towards the intended meaning.

4. Hybrid search: run both, then combine the rankings

Keyword search is good at exact codes, sizes, rare names and new terms the embedding model never saw. Vector search is good at meaning, synonyms and descriptions. The natural answer is to run both and merge the results.

Hybrid search. The same query runs through keyword search and vector search, each producing its own ranked list. Reciprocal rank fusion merges the lists using positions only, and an optional reranker then reorders the best candidates.

Why you cannot simply add the scores

The tempting way to merge is to add each product's keyword score and vector score. That is a common bug. A BM25 score of 1.028 and a cosine similarity of 0.82 are on completely unrelated scales: BM25 scores grow with query length and depend on the catalogue, while cosine sits between −1 and 1 and, as 12.6.2 explained, has a model-specific typical range. Adding them lets whichever scale happens to be bigger decide everything.

Reciprocal rank fusion

The standard fix ignores the scores and uses only the positions. Reciprocal rank fusion, RRF, introduced by Gordon Cormack and colleagues in 2009, gives each product, from each list it appears in, the amount 1 / (k + \text{rank}), and adds them up:

\text{RRF}(d) = \sum_{\text{lists}} \frac{1}{k + \text{rank}(d)}

Read it as "for each list, one over (k plus this product's position in it), added over all the lists". The constant k is usually 60, the value from the original paper. It stops first place from completely overpowering second place: with k = 60, rank 1 gives 1/61 \approx 0.0164 and rank 2 gives 1/62 \approx 0.0161, so being near the top of both lists matters more than being first in one.

Work it through with the two lists in the figure:

• A54 charger: rank 1 in both, 1/61 + 1/61 \approx 0.0328.
• Charger cable: rank 3 and 2, 1/63 + 1/62 \approx 0.0320.
• A54 back cover: rank 2 and 4, 1/62 + 1/64 \approx 0.0318.
• iPhone charger: rank 4 and 3, 1/64 + 1/63 \approx 0.0315.

The exact A54 charger stays first, because both methods agree on it. The back cover, which keyword search pushed up and vector search pushed down, drops from second to third. RRF needs no tuning, no knowledge of score scales, and works with any number of lists, which is why it is the default. When you have labelled data, you can do better by learning how to combine signals, which is the job of the ranking models in Chapter 12.12.6.

def rrf(*ranked_lists, k=60):
    scores = {}
    for lst in ranked_lists:
        for rank, item in enumerate(lst, start=1):                # (1) positions start at 1
            scores[item] = scores.get(item, 0.0) + 1 / (k + rank) # (2)
    return sorted(scores, key=scores.get, reverse=True)           # (3)

keyword = ["A54 charger", "A54 back cover", "charger cable", "iPhone charger"]
vector  = ["A54 charger", "charger cable", "iPhone charger", "A54 back cover"]
print(rrf(keyword, vector))
# → ['A54 charger', 'charger cable', 'A54 back cover', 'iPhone charger']

Line (1) walks each list with positions starting at 1. Line (2) adds that list's contribution for the item; an item missing from a list simply gets nothing from it. Line (3) sorts by total. Many search engines and vector databases now offer hybrid search with RRF built in.

Learned sparse retrieval, briefly

There is a middle path worth knowing by name. Models such as SPLADE use a transformer to produce a sparse vector for each text, like a keyword index, but with learned weights, and they also add related words that do not literally appear ("sneakers" might add weight to "shoes" and "running"). The result can be searched with an ordinary inverted index and captures some meaning. It is a useful option when you want keyword-style infrastructure with better recall, though the plain BM25-plus-embeddings hybrid remains the most common setup.

5. The full product search pipeline

Putting this chapter together, Cartwise's product search runs in stages, each cheap enough for its job:

1. Clean the query: lower-case, fix obvious typos, expand known synonyms, and recognise structured parts such as sizes or model numbers.
2. Retrieve candidates in parallel: BM25 for the top 200 by keywords, the vector index of 12.6.3 for the top 200 by meaning, both with the in-stock and delivery filters applied.
3. Fuse the two lists with RRF.
4. Rerank the best 50 with a slower, more accurate model that reads the query and each product together, called a cross-encoder and explained in Chapter 12.9.3.
5. Apply business rules: boost sponsored or fast-delivery products within limits, remove duplicates, diversify brands.

This shape, cheap broad retrieval followed by narrower and more expensive ranking, is called a retrieval funnel, and it is the same in web search, recommendations and the retrieval step of RAG. How to measure whether each stage is doing its job, with numbers like precision at 10 and nDCG, is covered in Chapter 12.9.5, and the complete case study is Chapter 12.15.2.

What the interviewer will push on

"Why not just use vector search?" They are checking that you know where embeddings fail: exact identifiers, model numbers, sizes, rare names and new vocabulary. A strong answer gives a concrete failing query and says hybrid search is the default.

"How does BM25 differ from TF-IDF?" They want term-frequency saturation through k_1 and length normalisation through b, explained in plain words rather than recited.

"How do you combine keyword and vector results?" The answer is rank fusion, because the two score scales are incomparable, with RRF and k = 60 as the standard. Adding raw scores is the common wrong answer.

"How do you handle typos?" A good answer separates spelling similarity (edit distance, trigrams, fuzzy queries) from meaning similarity (embeddings), and notes that subword tokenisation gives embeddings partial typo tolerance.

Volunteer this: look at your search logs for queries that return zero results. They are the cheapest map of what your search cannot do, and in product search they are dominated by model codes, typos and words in other languages, each of which points at a different fix.

Recall

• Embeddings blur exact surface details, so they fail on model numbers, sizes and rare names; keyword search is the reverse. Hybrid search uses both.
• Keyword search uses an inverted index from each word to the products containing it. BM25 scores matches with rarity (IDF), a saturating term count (k_1), and length normalisation (b). In the worked example it ranked the exact A54 charger first but an A54 back cover second.
• Typos: edit distance (Levenshtein, a dynamic program) and character n-grams measure spelling similarity; embeddings measure meaning, and subword pieces give them some typo tolerance. "Running shoes" is 2 edits from "running sores" but close in meaning to "sneakers".
• Do not add BM25 and cosine scores; their scales are unrelated. Reciprocal rank fusion adds 1/(k + \text{rank}) over lists with k = 60.
• Production search is a funnel: clean the query, retrieve with both methods under filters, fuse, rerank the top few dozen with a cross-encoder, then apply business rules.

Self-test: Why does a product saying "charger" twice score only slightly more than one saying it once? Using RRF with k = 60, what does an item ranked 1st in one list and absent from the other score? Give a query where edit distance would make results worse.

Next: 12.7.1 The Journey of a Prompt — embeddings, attention and softmax have all appeared separately; Chapter 12.7 assembles them into a large language model, starting with the whole path a prompt takes from text to answer.