Chunk, score and fuse a retrieval set

Retrieval is three small functions and one bad habit

Between the embedding model and the language model sits a pipeline that is almost entirely arithmetic: cut the documents up, score the pieces against the query, keep the best few, and merge the results of however many retrievers you are running. None of it needs a library, and writing it once is the difference between using a retrieval stack and being able to debug one. The bad habit in the title is the last step, and it is the one that quietly decides what your model gets to read.

Chunking, and why the windows overlap

A retriever scores whole chunks, so a chunk has to be small enough to be about one thing and large enough to stand on its own. Cut a document into adjacent, non-overlapping pieces and every boundary lands in the middle of some sentence, splitting a claim from the qualifier that made it true. Overlapping windows buy that back: consecutive chunks share their last few tokens, so a statement that straddles a boundary survives whole inside one of them.

The units here are tokens, and for this lesson a token is a whitespace-separated word. Real tokenizers differ, and the arithmetic does not.

def windows(tokens, size, overlap):
    step = size - overlap
    return [tokens[start:start + size] for start in range(0, len(tokens), step)]


print(windows(["a", "b", "c", "d", "e"], 3, 1))
# [['a', 'b', 'c'], ['c', 'd', 'e'], ['e']]

Two things fall out of that. The step is size - overlap, not size, and getting that wrong is the most common chunking bug there is. And the last window can be a stub: ['e'] here adds no token that ['c', 'd', 'e'] did not already carry, so it is an extra row in the index that can never be the best answer to anything.

Cosine similarity is a normalized dot product

An embedding is a vector. Two vectors are similar when they point the same way, which is measured by the angle between them, not by the distance. Cosine similarity is the dot product divided by both lengths, so it is the dot product with the magnitudes taken out.

import math


def cosine(left, right):
    dot = sum(a * b for a, b in zip(left, right))
    left_norm = math.sqrt(sum(a * a for a in left))
    right_norm = math.sqrt(sum(b * b for b in right))
    if left_norm == 0 or right_norm == 0:
        return 0.0
    return dot / (left_norm * right_norm)


print(round(cosine([1, 1, 0], [2, 2, 0]), 4))   # 1.0, same direction, different length
print(round(cosine([1, 0, 0], [1, 1, 0]), 4))   # 0.7071
print(round(cosine([1, 0, 0], [0, 1, 0]), 4))   # 0.0, at right angles

zip walks two sequences in step, and it stops at the shorter one, which is why mismatched dimensions give a wrong answer rather than an error. The zero-length guard is not decoration either: an all-zero vector has no direction, so the division would raise ZeroDivisionError on a document that happens to embed to zeros.

Top-k needs a tie-break or it is not reproducible

Scoring gives you a number per candidate. Taking the best few is a sort, and a sort needs to say what happens when two scores are equal, or the same query returns a different order depending on how the dictionary was built.

scored = [(0.9, "b"), (0.7, "c"), (0.9, "a")]
scored.sort(key=lambda pair: (-pair[0], pair[1]))
print(scored)         # [(0.9, 'a'), (0.9, 'b'), (0.7, 'c')]

The key returns a tuple, so Python compares the first element and falls through to the second only on a tie. Negating the score sorts it descending while the id stays ascending, which is one sort rather than two.

Two retrievers, two scales, one answer

Production retrieval runs at least two retrievers over the same query: a dense one over embeddings, which finds passages that mean the right thing, and a sparse keyword one, which finds passages containing the exact rare term the user typed. They are good at different failures, so you want both. Now you have two ranked lists and have to produce one.

The obvious merge is to add each document's two scores together. Look at what the two retrievers actually return:

dense   = {"p1": 0.81, "p2": 0.79, "p3": 0.78}   # cosine, between -1 and 1, positive throughout here
keyword = {"p2": 18.4, "p4": 12.1, "p1": 3.2}    # BM25, no upper bound at all

Normalizing first is the usual next suggestion, and it is harder than it looks: min-max normalization needs both full score distributions, it changes with every query, and it still has nothing to say about a document one retriever never returned. The two scores are not measurements of the same quantity, and no amount of rescaling makes them one.

Reciprocal rank fusion

What the two lists genuinely share is position. Both of them said "this is my first, this is my second", and that statement means the same thing in both. So throw the scores away and fuse the ranks:

def reciprocal_rank_fusion(rankings, k=60):
    fused = {}
    for ranking in rankings:
        for position, doc in enumerate(ranking):
            fused[doc] = fused.get(doc, 0.0) + 1.0 / (k + position + 1)
    return fused


print(reciprocal_rank_fusion([["p1", "p2"], ["p2", "p1"]], k=60))
# {'p1': 0.03252247488101534, 'p2': 0.03252247488101534}

Those two totals are identical, and the tie is the point. The two rankings are mirror images, so each document holds one first place and one second place, and 1/61 + 1/62 is what that is worth whichever list it came from. Rank fusion is symmetric in a way that adding scores never is.

That is the whole algorithm. Three properties are worth naming because each is doing a job:

• dict.get(doc, 0.0) starts a document at zero the first time it is seen, so a document in one list only is scored rather than dropped. The "merge the documents both lists agree on" version of this loop is the second bug in the practice.
• position + 1 makes ranks count from one. Off by one here and the top result of every list divides by k instead of k + 1, which is survivable, but the rank-zero document gets an outsized share.
• k, conventionally 60, damps the top. It sits in the denominator, so it sets how steeply a document's contribution falls off from one rank to the next: at 60 the gap between rank 1 and rank 2 is 1/61 against 1/62, tiny enough that agreement between retrievers matters more than any single retriever's confidence. That is the entire design goal, and the size of the constant is what buys it.

The fused score has no meaning on its own. It is not a probability, not a similarity, and not comparable between queries. It exists to order one result set, and that is all it is for.

Pitfalls

• overlap must be strictly less than size. Equal gives a step of zero; greater gives a negative step and a ValueError from range.
• Rounding a score for display is fine. Rounding it before you sort creates ties that were not there, and then the tie-break decides the ranking.
• list.index(doc) gives a position, so a rank is index + 1. It also raises ValueError when the document is absent, and absent is a real case, so check membership first.
• Fusing three rankings is the same loop with a longer list. Fusing the same ranking twice is not: it doubles that retriever's vote, which is a weighting decision made by accident.

Interview nuance: the follow-up is usually "so when would you not use rank fusion?" Two answers hold up. When one retriever is known to be much better on your traffic, rank fusion throws that away, and a weighted variant or a proper reranking model is the better trade. And when you have a cross-encoder budget, fusion is only the candidate-generation step: it decides which twenty passages are worth the expensive rerank, and the rerank decides the order. Being able to name fusion as cheap, unsupervised and scale-free, and to say what you would give up by replacing it, is the answer being probed for.

Sources: The reciprocal rank fusion paper · math.sqrt · Sorting techniques