FINDING NEEDLES · CHAPTER 09

Reranking

A fast retriever reads the question and each answer apart. That is why it is fast, and why it cannot see the word “no”. A second, slower model reads them together, but only for the few answers that made the cut.

~14 min read8 FAQ answersTested Python

What you'll learn

  • How a bi-encoder and a cross-encoder differ: apart versus together
  • Why a bi-encoder can rank “no balcony” above “a balcony”
  • How retrieve-then-rerank splits the work into two stages
  • Why the cross-encoder only ever sees the top k, and what that costs

Before you start

Skim the shelf, then read the four that looked right

A guest asks the hotel chatbot: “Do you have rooms with a balcony?” The FAQ has eight answers. You could read all eight slowly and carefully. With eight that is fine. With a million it is not.

So you do it in two passes. First a quick skim that picks a handful of likely answers. Then a careful read of just that handful, which puts them in the right order.

Stage 1 must be cheap per document, so it judges each answer without looking at the question. Stage 2 is allowed to be expensive per document, because it only runs on a few. Reading the question and the answer side by side is what lets it notice that “no balcony” is the opposite of what was asked.

Apart or together

Bi-encoder

Encode the question to a vector. Encode each answer to a vector, once, before any question arrives. The score is a dot product or cosine.

O(k) · small k · recall

MANIM Cross-encoder cost is O(k); keep k small after dense recall.

skim · joint · top-k · precision

MANIM Rerank: skim with bi-encoder, read top-k with cross-encoder.

One model pass per query, plus a vector search. The answer never sees the question.

Cross-encoder

Glue the question and one answer into a single input, like [CLS] question [SEP] answer [SEP]. One transformer reads it. A small head turns the result into a single relevance score.

Every question word can attend to every answer word. Nothing can be computed before the question arrives.

In this chapter both scorers are hand-written toys, so you can check every number. The toy bi-encoder turns a text into the set of its words, after dropping common words like “the” and “have”. It is crude, but it has the property that matters: each side is encoded alone. The toy cross score reads both word lists together and follows one rule a real cross-encoder learns from data: a word the answer negates counts against it.

shared words, divided by the root of both sizes. That is cosine on two 0/1 vectors. Wq and Wd are the word sets.

each question word the answer supports is +1, each one it negates is −1, averaged over the question.

The bi-encoder picks the wrong answer

After dropping common words, the question is just {rooms, balcony}. Stage 1 scores every answer.

IdFAQ answerWords keptBi score
1Standard rooms have no balcony.standard, rooms, no, balcony0.707
2Corner rooms come with a private balcony and a lake view.corner, rooms, come, private, balcony, lake, view0.535
3All rooms have free wifi.rooms, free, wifi0.408
8No rooms face the road.no, rooms, face, road0.354
4The balcony bar opens at 6 pm.balcony, bar, opens, 6, pm0.316
5, 6, 7Breakfast, pets, late checkoutno shared word0

Answer 1 shares both words in a short text, so it wins with 2 / √(2 × 4) = 0.707. The answer the guest needs, answer 2, shares the same two words in a longer text and scores 0.535.

Look at what “no” did. It is just one more word in answer 1’s vector, a word the question does not have. Delete it and the answer “Standard rooms have a balcony.” scores 0.816. So the negation lowered the score only by making the text longer. The meaning flipped; the score barely moved. Learned bi-encoders are far better than a word set, but they share the limit: the answer’s vector is fixed before the question exists, so any interaction between the two has to be guessed in advance.

Four candidates, one careful read each

QuestionDo you have rooms with a balcony?
Stage 1 · bi-encoder over all 8keep top k = 4 · real systems: about 100 from millions
Stage 2 · cross score on each candidate4 cross passes
Show the top 2real systems: about 5 to 10
IdStage-1 rankCross readingCross scoreNew rank
22rooms +1, balcony +11.01
33rooms +1, balcony missing0.52
11rooms +1, “no balcony” −10.03
84“no rooms” −1, balcony missing−0.54

The right answer moves from second to first. The trap answer drops from first to third and leaves the top 2. Answer 4, the balcony bar, would also score 0.5, but stage 1 never passed it on. The reranker can only reorder what it is given.

Interactive · How many to pass on

Set k, the number of stage-1 candidates the reranker reads. What happens to the final top 2 when k is 1?

At k = 1 the reranker only sees answer 1 and has nothing better to promote. At k = 2 answer 2 gets in and goes straight to the top. Past that, a bigger k only costs more passes here. In a real system you choose k by checking how often the right answer is anywhere in the top k of stage 1: that is the ceiling on what the reranker can fix.

Why the careful reader only gets 100

A bi-encoder encodes every document once, offline. At query time it runs the model once, on the question, then does a vector search. A cross-encoder has nothing to store ahead of time. Every candidate needs its own pass with this question in it.

candidates times the time for one cross-encoder pass on a question–answer pair. It grows with k, not with the size of the collection.

Take a collection of 1,000,000 passages and assume 5 ms per cross-encoder pass. Scoring all of them for one question is 1,000,000 × 5 ms = 5,000 seconds, about 83 minutes. Scoring the top 100 is 0.5 seconds. That is 10,000 times less work, and batching the 100 pairs on a GPU brings the wall-clock time down further. The 5 ms is an assumption for the arithmetic; the ratio is what matters.

The middle ground: late interaction

A cross-encoder lets words meet inside the model. A bi-encoder squeezes each side into one vector first. Late interaction, the idea behind ColBERT, sits between them. It keeps one vector per token for each document, computed offline. At query time each question token finds its most similar document token, and those best matches are added up. Word-level matching survives, and the document side can still be stored. The price is storage: many vectors per document instead of one. It can serve as stage 1 or as a cheaper stage 2.

Both stages you can re-run

rerank.pytop 2 after rerank: 2, 3
"""Retrieve wide with a toy bi-encoder, then rerank with a toy cross score.

Both scorers are hand-written stand-ins, not neural models.
The bi-encoder turns each text into a vector on its own.
The cross score reads the query and the answer together, so it can see "no balcony".
"""
import math

# A small hotel FAQ. Ids match the tables on the page.
FAQ = {
    1: "Standard rooms have no balcony.",
    2: "Corner rooms come with a private balcony and a lake view.",
    3: "All rooms have free wifi.",
    4: "The balcony bar opens at 6 pm.",
    5: "Breakfast is served from 7 to 10.",
    6: "Pets are welcome for a small fee.",
    7: "Late checkout costs 20 euros.",
    8: "No rooms face the road.",
}

QUERY = "Do you have rooms with a balcony?"

STOP = {"a", "the", "is", "are", "have", "with", "and", "for", "at",
        "from", "to", "all", "do", "you"}
NEGATORS = {"no", "not"}


def tokenize(text):
    """Lowercase, strip end punctuation, drop stop words. Order is kept."""
    words = [w.strip(".,?!") for w in text.lower().split()]
    return [w for w in words if w and w not in STOP]


def encode(text):
    """Toy bi-encoder: the set of words. It never sees the other side."""
    return set(tokenize(text))


def bi_score(q_vec, d_vec):
    """Cosine of two 0/1 vectors: shared words over the root of both sizes."""
    return len(q_vec & d_vec) / math.sqrt(len(q_vec) * len(d_vec))


def cross_score(query, doc):
    """Toy cross-encoder: read the pair together.

    Each query word found in the answer counts +1, or -1 if the answer
    says "no" or "not" right before it. Divide by the query length.
    """
    q_words = tokenize(query)
    d_words = tokenize(doc)
    total = 0
    for word in q_words:
        if word not in d_words:
            continue
        i = d_words.index(word)
        negated = i > 0 and d_words[i - 1] in NEGATORS
        total += -1 if negated else 1
    return total / len(q_words)


def retrieve(query, k):
    """Stage 1. Document vectors could be built once, before any query."""
    doc_vecs = {i: encode(text) for i, text in FAQ.items()}
    q_vec = encode(query)
    scored = [(i, bi_score(q_vec, v)) for i, v in doc_vecs.items()]
    scored.sort(key=lambda row: -row[1])
    return scored[:k]


def rerank(query, candidates, keep):
    """Stage 2. One cross pass per candidate. Ties keep the stage-1 order."""
    scored = [(i, cross_score(query, FAQ[i])) for i, _ in candidates]
    scored.sort(key=lambda row: -row[1])
    return scored[:keep], len(candidates)


def cost_seconds(n_docs=1_000_000, k=100, ms_per_pass=5):
    """Cross-encoder on every document versus on the top k only."""
    return n_docs * ms_per_pass / 1000, k * ms_per_pass / 1000

Mistakes learners make

Expecting the reranker to find what stage 1 missed. It only reorders its input. Answer 4 scores 0.5 on the cross reading but never got in. Measure recall at k for stage 1 before tuning stage 2.

Running a cross-encoder over the whole collection. One pass per document per question is 5,000 seconds on a million passages at 5 ms each. It belongs on a short list.

Mixing the two scores as if they were on one scale. The bi score of answer 1 is 0.707; its cross score is 0.0. They measure different things. Rank by the reranker’s score, or fuse by rank (chapter 10), not by adding raw numbers.

Feeding the reranker more text than it can read. A cross-encoder has a maximum input length. A long passage gets cut off, and the part that answers the question may be in the cut. Rerank chunks, not whole documents.

What to remember

  • A bi-encoder encodes the question and each answer apart. Answer vectors can be built ahead of time, so stage 1 is fast.
  • Because the sides never meet, “no balcony” scored 0.707 and beat the right answer at 0.535.
  • A cross-encoder reads the pair together. The toy cross score put answer 2 first at 1.0 and dropped answer 1 to 0.0.
  • Retrieve wide, rerank narrow: here 8 → 4 → 2, with 4 cross passes. In practice about 100 → 5.
  • Rerank time grows with k. All 1,000,000 passages would take 5,000 seconds; the top 100 take 0.5 seconds.

Check yourself

1. Why can a bi-encoder store its document vectors before any query, and a cross-encoder cannot?

The bi-encoder’s document vector does not depend on the query. The cross-encoder’s output is a function of the pair, so it only exists once the query is known.

2. Why did answer 1 beat answer 2 in stage 1?

Both share rooms and balcony. Answer 1 is shorter, so its cosine is higher. The “no” is just an extra word that does not match.

3. With k = 1, what does the reranker return first?

Answer 1, with a cross score of 0.0. It is the only candidate, so there is nothing to promote over it.

4. Your reranked results are often wrong even though the reranker is strong. What do you check first?

Whether the right answer is in stage 1’s top k at all. If not, raise k or improve stage 1, for example with hybrid search.

Go to the source

Keep going