Cross-Encoder Reranking and the Cost of Reading Every Pair

A dual encoder computes a query vector and a document vector independently and compares them with a dot product. That independence is what makes it fast: document vectors are computed once at index time, and a query costs one encoder pass plus a search over precomputed vectors. It is also what limits it. The document vector must be a summary of the document that is useful against any query, because it is computed without knowing which query will arrive. Two documents that differ in the one clause that answers a specific question receive nearly identical vectors if the rest of their text is similar, and no amount of index tuning separates them.

A cross-encoder removes the independence. It concatenates the query and the passage into one input, runs a transformer over the pair, and produces a single relevance score from the pooled representation. Attention now spans both texts, so every query token can attend to every passage token and the representation of the passage is conditioned on the question being asked. The model can represent “this passage answers this question” rather than “this passage is about the same topic as this question”, and those are different predicates.

The cost of that conditioning is that nothing can be precomputed. Every query-passage pair is a fresh forward pass, so a cross-encoder over a million-document corpus is a million forward passes per query. That is why it is used as a second stage over a shortlist produced by a cheap first stage, and why the size of that shortlist is the single most consequential parameter in the design.

The mechanics of scoring a pair

The input format is a sequence of the form query tokens, a separator, and passage tokens, truncated to the model’s maximum length. A special classification token sits at the front, and its final hidden state is projected to a scalar. The model is trained with a binary or graded relevance objective over labelled pairs, so its output is a logit rather than a similarity: larger means more relevant, the scale is arbitrary, and it is not comparable across models.

Two consequences follow from the truncation. A passage longer than the remaining budget after the query is cut, and the cut portion is invisible to the scorer, so a reranker applied to whole documents scores only the first few hundred tokens. This is an argument for reranking chunks rather than documents, and it interacts with chunk size: a 2,000-token chunk exceeds the budget of a typical reranker and is silently truncated to its opening, which may be a heading and an introduction rather than the answer. The second consequence is that query length consumes the same budget, so a long query with appended conversation history leaves less room for the passage, and the effective recall of the reranker falls as the query grows.

Throughput comes from batching. The pairs in a shortlist are independent, so they can be packed into one forward pass up to whatever the accelerator’s memory allows, and the marginal cost of an additional candidate is small once the batch is formed. A shortlist of 50 scored as one batch of 50 costs roughly one forward pass over 50 times the sequence length, which is far cheaper than 50 separate passes but still proportional to the total token count. The latency therefore scales with candidates times average pair length, and the average pair length is dominated by the passage.

import torch

def rerank(query, candidates, model, tokenizer, max_len=512, batch=32):
    # candidates: list of (chunk_id, text); returns ids sorted by relevance
    scored = []
    for i in range(0, len(candidates), batch):
        group = candidates[i:i + batch]
        enc = tokenizer(
            [query] * len(group),
            [text for _, text in group],
            truncation="longest_first",   # trims the passage, not the query
            max_length=max_len,
            padding=True,
            return_tensors="pt",
        )
        with torch.no_grad():
            logits = model(**enc).logits.squeeze(-1)
        for (chunk_id, _), s in zip(group, logits.tolist()):
            scored.append((s, chunk_id))
    scored.sort(key=lambda t: (-t[0], t[1]))
    return [cid for _, cid in scored]

The longest_first truncation strategy is a deliberate choice, not a default to accept blindly. Trimming the passage preserves the query, which is usually what matters, but it means a long passage is scored on its opening. Some tokenizers default to trimming whichever side is longer; that can cut the query and change the ranking for reasons unrelated to the passage.

Candidate depth is the whole trade

The reranker’s benefit is bounded by what the first stage hands it. If the relevant chunk is not in the shortlist, the reranker cannot promote it, and the final answer quality is exactly the first stage’s recall at the shortlist depth. Increasing depth raises that ceiling and costs linearly in reranker work.

The shape of the curve explains the usual operating range. First-stage retrieval recall at 20 is typically high for a well-tuned hybrid system; recall at 100 is higher but the increment is smaller, because the additional candidates are mostly marginal. Going from 20 to 100 candidates quintuples reranker cost for a few points of ceiling. Going from 20 to 10 halves cost while cutting the ceiling substantially, because rank 10 to 20 is where the remaining relevant documents concentrate. This is why shortlists in the tens rather than the hundreds are the common configuration, and why the exact number should be chosen from a measured recall-versus-depth curve for the actual corpus rather than from a default.

A cheaper variant is to score with a smaller model and then rescore the top few with a larger one. The small model has lower per-pair cost and lower discrimination; the large model sees only a handful of pairs, so its cost is bounded. The two-stage cascade is not free in quality, because the small model’s errors remove candidates the large model never sees, but it shifts the cost curve favorably when the accelerator is saturated.

Late-interaction models occupy a middle position. They precompute per-token vectors for each passage, then at query time compute a maximum-similarity score for each query token against the passage’s token vectors and sum those maxima. That is more expressive than a single passage vector, because it preserves token-level detail, and cheaper than a cross-encoder, because the passage side is precomputed and the query-time work is a matrix operation rather than a transformer pass. The storage cost is the reason it is not universal: one vector per token is two to three orders of magnitude more data than one vector per chunk.

What the score means and what it does not

A reranker logit is a ranking signal, not a probability, unless the model was calibrated. Sorting by it is safe; thresholding against a fixed value is not, because the logit scale depends on the model, the training data, and the input length. A threshold chosen to admit “confident” matches on one corpus will admit everything or nothing on another. The remedy, when a threshold is genuinely needed for abstention, is to calibrate on held-out pairs and to record the calibration with the model version.

Ranking by the logit also loses the first stage’s information. A hybrid first stage produces evidence from two independent systems, and the reranker sees only text. A chunk that the lexical system ranked first because it contains an exact identifier, and that the dense system missed, may receive a mediocre reranker score because the reranker does not know about the lexical evidence. Keeping the first-stage rank as a feature, or blending it with the reranker score at a small weight, preserves that evidence; discarding it entirely is a common and avoidable loss.

There is also a distribution problem. A reranker trained on short queries against Wikipedia-style paragraphs is applied to multi-sentence questions against code and log files, and the input distribution differs in length, formatting, and vocabulary. The model does not fail loudly; it produces scores that are less informative, and the top of the reranked list looks similar to the first stage’s order. Detecting this requires evaluating reranker output against a labelled sample from the actual domain, and the sample has to include the awkward cases, which is the same evaluation problem the rest of the pipeline has.

Placement in the serving path

The reranker is a separate model, often a separate process, and its placement determines whether it adds latency serially or in parallel with other work. The first stage must finish before reranking begins, so the two stages are strictly ordered. Everything else can overlap: the prompt assembly for previously retrieved context, the tokenisation of the query, and any cache lookups.

The reranker’s memory footprint is modest compared with the generative model, since a reranking model is typically two to three orders of magnitude smaller in parameter count, but it competes for the same accelerator. Co-locating it with the generator means the two contend for memory bandwidth and for batch slots; running it on a CPU is viable for small models and becomes the bottleneck for larger ones. Serving it as a separate pool keeps the latency predictable at the cost of a network hop, and the hop is usually a small fraction of the reranking time.

Caching is the obvious optimisation and the one with the sharpest correctness caveat. Caching reranker scores keyed by query and chunk is valid only while the model, the chunk text, and the truncation configuration are all unchanged. A model update invalidates every cached score, and serving stale scores against a new model produces a ranking that is neither the old model’s nor the new one’s. Keying the cache on the model revision makes the invalidation automatic, and the same discipline applies to the embedding revision recorded with the index, as described in Similarity Metrics and the Normalisation They Require.

The last placement question is whether reranking is worth its latency at all. The answer depends on what the generator does with the context. If the prompt contains twenty chunks and the model must find the one that matters, a better ordering helps, but only if the ordering changes which chunks fit inside the token budget. If all twenty fit, the reranker’s contribution is to the model’s attention rather than to the selection, and that contribution is smaller and less reliable, which is the phenomenon treated in Context Dilution. Reranking pays when the budget forces a cut, and the cut is where the ranking becomes the answer.