Cruxly › AI engineering › Retrieval and RAG

Hybrid Search, Rerankers and Late Interaction

BM25 by hand, RRF by hand, the cost of a reranker, and a 200 ms budget you can defend

Prompt: "Our catalogue has 400,000 product SKUs and 8,000 long manuals. Dense search misses exact part numbers and BM25 misses paraphrases. Why hybrid? How does reciprocal rank fusion work? Compare bi-encoder, cross-encoder and ColBERT. The reranker adds 200 ms: is it worth it? Design the retrieval stack."

40 minutes first. Compute one BM25 score, one RRF fusion, one rerank token bill and one latency budget by hand. The trap is answering each question with a tool name instead of a number and a way to prove the stage earns its place.

BM25 in one formula, and what it catches that vectors miss

BM25 scores a document by summing, over the query's terms, a rarity weight times a saturating count, adjusted for document length. For one term:

score = idf x tf x (k1 + 1) / (tf + k1 x (1 - b + b x dl / avgdl))

with the usual defaults k1 = 1.2 and b = 0.75. Work it with a 1,000-document corpus.

Rarity (idf). idf = ln(1 + (N - df + 0.5) / (df + 0.5)), where df is the number of documents containing the term. A term in 10 documents: ln(1 + 990.5 / 10.5) = 4.557. A term in 900 documents (a word like "the" in policy text): 0.106. A term in only 1 document, say a part number: 6.503. The rare term is worth 61 times the common one.

Saturation (tf). The fraction tf x 2.2 / (tf + 1.2) for a document of average length: 1 occurrence gives 1.00; 3 gives 1.57; 6 gives 1.83; 12 gives 2.00. It can never exceed k1 + 1 = 2.2. Repeating a word twelve times does not make a document twice as relevant as repeating it six times; that is the point.

Length normalisation (b). The same 3 occurrences in a document twice the average length give 3 x 2.2 / (3 + 1.2 x (0.25 + 1.5)) = 1.294 instead of 1.571. With the idf of 4.557, scores are 4.557 x 1.571 = 7.16 for the average-length document and 5.90 for the long one. A long manual that mentions your term three times is less likely to be about it than a short note that does.

What it catches. Exact tokens: part numbers like KX-4471-B, error codes, names, acronyms, statute sections, function names. These are rare strings with a huge idf, and a dense vector smears them. Embeddings and Similarity explains why: the contrastive objective rewards topic, not character-level identity. What it misses: paraphrase and synonyms ("laptop" versus "notebook"), cross-lingual matches, and anything where the query has no word in common with the passage.

The BEIR paper (18 datasets, zero-shot) calls BM25 a robust baseline and reports that dense and sparse neural retrievers often underperformed other approaches there, which is the empirical reason you do not drop the lexical leg. Treat that as a result on those datasets and test it on yours: Choosing, Evaluating and Fine-Tuning an Embedding Model gives the method.

Fusion: reciprocal rank by hand, and why raw scores cannot be added

Reciprocal rank fusion (RRF) scores each document by summing 1 / (k + rank) over the lists it appears in, with k = 60. The constant comes from the original RRF paper (Cormack, Clarke and Buettcher, SIGIR 2009), which says k = 60 was fixed during a pilot investigation and not altered afterwards: it is a sensible default, not a derived optimum, so tune it on your golden set. It damps the gap between rank 1 and rank 2 so that no single list dominates.

Work the example. Dense ranks A, B, C; sparse ranks C, A, D.

A: 1/(60+1) + 1/(60+2) = 0.016393 + 0.016129 = 0.032522   (dense rank 1, sparse rank 2)
C: 1/(60+3) + 1/(60+1) = 0.015873 + 0.016393 = 0.032266   (dense rank 3, sparse rank 1)
B: 1/(60+2)            = 0.016129                          (dense only)
D: 1/(60+3)            = 0.015873                          (sparse only)
fused order: A, C, B, D

A document ranked well by both legs beats one ranked first by one leg and absent from the other. A beats C by a hair, 0.0325 against 0.0323: each has one rank-1 term worth 1/61, and A's other term is rank 2 (1/62) while C's is rank 3 (1/63). Documents in only one list (B, D) always fall behind those in both, which is the consensus effect you want.

Why not add the raw scores? A cosine of 0.82 and a BM25 score of 14.3 are on unrelated scales. The usual patch is min-max normalisation, and it is fragile. Take three documents: cosines [0.82, 0.80, 0.78] normalise to [1.0, 0.5, 0.0], and BM25 [14.3, 9.1, 2.0] to [1.0, 0.58, 0.0]. Now let one document with BM25 40.0 enter the list (a very long document with repeated terms): the same three BM25 scores normalise to [0.32, 0.19, 0.0]. The leg's influence on the other documents shrinks by two thirds because of an outlier that has nothing to do with them. Rank-based fusion cannot be perturbed that way, because it only reads order.

RRF has its own costs. It throws away magnitude: a dense leg that is hugely confident (0.95) about one document and merely lukewarm about the rest produces the same ranks as a leg that is uncertain about everything. You can weight the legs (w x 1/(k + rank)), tune k on the golden set, and widen the fusion depth. Depth matters: take the top 50 to 100 from each leg, not 10, or a document ranked 12th on one leg and 3rd on the other is lost before fusion. The bounded candidate list then goes to the reranker, as in Multi-Tenant, Multilingual RAG at Scale.

:::warn Do not tune fusion weights on the queries you use to report the final score. With a few hundred queries, a weight sweep fits noise. Tune on one split of the golden set and report on a held-out split, per Evaluation Gates That Actually Block a Bad Deploy. :::

Cross-encoder rerankers: the cost model and where to cut the list

A bi-encoder embeds the query and each passage separately, and a cross-encoder feeds the query and one passage into the model together. The bi-encoder's passage vectors are computed once, offline, which is why a hundred million of them are searchable. The cross-encoder must run its transformer on every (query, passage) pair at query time, with full attention between the two texts, which is why it is more accurate on fine distinctions (negation, numbers, who did what) and why you can afford it only on a short list. The approach for BERT-style rerankers is in "Passage Re-ranking with BERT" (Nogueira and Cho, 2019). BEIR found that re-ranking and late-interaction models achieved the best zero-shot results on average, at a high computational cost.

The cost model is candidates x tokens. Rerank 50 candidates of 400 tokens: 20,000 tokens through the model per query (plus the query repeated 50 times, a small extra). At a million queries a day that is 20 billion tokens a day of reranker compute. Doubling the candidates to 100 doubles it; moving to 1,000-token chunks (50 x 1,000 = 50,000) multiplies it by 2.5. Latency does not scale linearly, because pairs can be batched on a GPU, but it grows with both, and the longest pair in a batch sets the padding.

Where to cut the candidate list. Do not guess: sweep N = 10, 25, 50, 100, 150, running first-stage, then the reranker on the top N, and plot final recall@5 against reranker milliseconds. The curve normally rises fast and then flattens, because a document ranked 90th by the first stage rarely becomes the correct top-5 result. Anthropic's contextual retrieval experiments reranked the top 150 and kept the top 20, which is one data point from one setup, not a rule.

Hosted versus self-served. A hosted reranking API charges per search or per token (check current prices; they vary by vendor and are not on this page) and adds a network hop. A self-served model on a GPU costs a fixed hourly rate that is cheap at high, steady load and wasteful when idle. Decide by dividing: queries per day x candidates x tokens against what one GPU can process.

How the reranker fails.

• Truncation. Pairs longer than the reranker's limit are cut, so a long chunk's answer in the second half is never seen.
• Domain shift. A reranker trained on web question answering can demote a manual snippet that has the exact torque value; test it on your golden set.
• Exact-identifier demotion. Natural-language rerankers may prefer a fluent paragraph over a terse spec line containing the exact SKU the BM25 leg found. If your ablation shows it, give the identifier leg a bypass: exact matches on a SKU field go straight to the top.
• Latency tail. A rerank step with p50 of 120 ms and p99 of 600 ms drives your overall p99; set a timeout and fall back to the fused order.

Late interaction and learned sparse: the middle of the spectrum

ColBERT-style late interaction keeps one vector per token instead of one per passage, and scores by matching each query token to its best document token. From the ColBERT paper (Khattab and Zaharia, 2020): encode the query into token vectors and the passage into token vectors offline; the relevance is MaxSim: for each query token take the maximum similarity over all document tokens, then sum.

Small example: 2 query tokens and 3 document tokens, with similarities [[0.9, 0.1, 0.2], [0.3, 0.2, 0.8]]. The best match for query token 1 is 0.9 and for token 2 is 0.8, so MaxSim is 0.9 + 0.8 = 1.7. A passage whose tokens are all moderately similar to everything (0.5 throughout) scores only 0.5 + 0.5 = 1.0. Finer matching than a single averaged vector, without the pair-at-a-time cost of a cross-encoder, because the document side is precomputed.

The price is storage. A 300-token passage at 128 dimensions in float16 is 300 x 128 x 2 = 76,800 bytes (76.8 KB) against 1,024 x 4 = 4,096 bytes for one float32 vector: 18.75 times more. For 20M passages, that is 1.536 TB versus 81.9 GB. Production systems compress token vectors and prune them, and later work reduces the footprint, but you should budget for an order of magnitude more storage and a more complex index than single-vector search. The same idea applied to page images (ColPali) retrieves from scanned documents without OCR, a promising option for visually rich PDFs that you should evaluate rather than assume.

Learned sparse retrieval (SPLADE) is the other middle option. SPLADE (Formal et al.) uses a masked language model to produce a sparse vector over the vocabulary: weights for the words in the text and for related words it expands to ("laptop" activates "notebook"). It is stored in an ordinary inverted index, so it keeps BM25's operational shape and exact-match behaviour while adding some synonym handling. The cost is encoding every document with a transformer at ingestion and denser postings lists.

When is late interaction worth it? When your ablation shows the reranker is the biggest gain, the candidate list is too long to rerank (a million candidates), or you cannot afford rerank latency. For most teams the order is dense + BM25 + cross-encoder first, because that stack is well supported; late interaction is the upgrade when you have the storage and an evaluation that says so.

A latency budget, and how each stage proves it earns its place

Write the budget as numbers and cut from the stage with the lowest gain per millisecond. An example stack, with assumed timings you must replace with measurements: query embedding 30 ms, ANN search 20 ms, BM25 15 ms, fusion 2 ms, reranker 150 ms.

If the two legs run in parallel, the critical path is max(30 + 20, 15) = 50 ms, then fusion and rerank: 50 + 2 + 150 = 202 ms, about 200. Run everything one after the other and it is 30 + 20 + 15 + 2 + 150 = 217 ms. The reranker is 74 percent of the total, so it is the first place to look: fewer candidates (50 to 25 roughly halves it), a smaller model, a timeout, or skipping it for queries where the first-stage top-1 score margin is large. An LLM call that follows takes seconds, so 200 ms of retrieval is not automatically a problem; in a streaming chat it delays the first token by 200 ms. Ask what the user feels, and what the SLO says.

The interview answer for "reranking adds 200 ms, is it worth it?" is not yes or no: "Show me the ablation. If reranking lifts recall@5 by 5 points on our golden set, that is 5 points of answers that are not built on the wrong chunk, against 200 ms on a path that already waits seconds for generation. I would take it, shrink the candidate list to where the curve flattens, and make it conditional."

The ablation that proves each stage. Hold the corpus, the golden set, the chunker and k constant. Add one stage per row:

The numbers above are made up to show how to read the table; they are not a benchmark. The reading rule: a stage stays only if its gain exceeds the error bar (about plus or minus 4 points at 300 queries, as the embedding lesson computed) and the points per 100 ms are worth it (here the rerank gives 7 points for 150 ms, about 4.7 per 100 ms). Contextual text (Chunking and Document Parsing) costs ingestion, not latency, so its price is paid elsewhere. Report the per-segment difference too: BM25 might lift SKU queries by 20 points and hurt paraphrase questions slightly; the average hides both.

Now design for the prompt. Product SKUs plus long manuals: a SKU field index with exact and prefix match (no ranking model needed for KX-4471-B), BM25 plus dense over structure-aware manual chunks with title paths, RRF at depth 50, a cross-encoder on 25 to 50 candidates only when the query is not a pure SKU lookup, and a golden set that has SKU queries, paraphrase queries and "which part fits model X" queries in labelled strata.

How to say it in the interview

"Dense vectors capture meaning and miss exact strings; BM25 captures exact strings and misses paraphrase, so I run both and fuse by rank, because their raw scores live on different scales. Then a cross-encoder reads the query and each of the top fifty candidates together, which is accurate and costs fifty times four hundred tokens per query, so I cap the candidate list and keep it off the path for easy queries. ColBERT-style late interaction sits between: better than one vector per passage, but ten to twenty times the storage. I would justify each stage by ablating on the golden set: dense only, plus BM25, plus rerank, plus contextual text, and keep a stage only if it beats the error bar for the milliseconds it costs."

Checklist

• Ran dense and BM25 legs in parallel by default
• Can compute BM25 by hand: idf, saturating tf, length normalisation
• Fused by reciprocal rank (k = 60) at depth 50 to 100 per leg, and tuned weights on a split, not the reporting set
• Costed reranking as candidates x tokens (50 x 400 = 20,000 tokens per query)
• Chose the candidate cut by sweeping N and cutting where recall flattens
• Set a reranker timeout with a fallback to the fused order
• Tested the reranker on exact identifiers, long chunks and my domain
• Budgeted storage before proposing ColBERT (about 76.8 KB per passage, 18.75x one vector)
• Wrote the latency budget with the critical path (parallel legs) and cut the largest stage first
• Ablated dense, +BM25, +rerank, +contextual on one golden set with per-segment results
• Gave exact SKU or ID lookups a bypass to a field index
• Labelled the vendor sources of any reranking gains I quoted

Related lessons

• RAG From Scratch, No Framework
• Chunking and Document Parsing: Structure-Aware Splits, Parent-Child, Late Chunking and Contextual Retrieval
• Choosing, Evaluating and Fine-Tuning an Embedding Model
• ANN Indexes in Depth: HNSW, IVF-PQ, DiskANN and the Recall/Latency/Memory Triangle
• Query Understanding and Agentic Retrieval: Rewriting, Routing, Multi-Hop and GraphRAG
• Multi-Tenant, Multilingual RAG at Scale