How do you size cross-encoder rerank depth k against a 400ms p95 latency budget?

## The cost model A cross-encoder scores one query-passage pair per forward pass. Rerank depth k therefore costs k forward passes, every query, online, with nothing cacheable across queries. That single fact is the whole latency story: rerank time is roughly linear in k and roughly superlinear in passage length, and it lands entirely inside the user's wait. Compare that with the first stage, where passage vectors were computed offline and the online work is an ANN lookup measured in single-digit milliseconds. Reranking is the first place in a retrieval pipeline where model compute scales with how many documents you are willing to consider. ## Work backwards from the end-to-end budget The budget belongs to the product, not to the reranker. Take a helpdesk assistant that must show its first token within 400ms at p95. Decompose: - query embedding: ~5ms - ANN search over the index, top-50: ~35ms - reranking those 50: ? - generator time-to-first-token with the selected passages in the prompt: ~220ms That leaves roughly 140ms. If a measured pair costs ~3ms at 512 tokens on your hardware, k lands near 45. Notice how little slack there is: the reranker is competing with the generator for the same wall clock, and the generator's prompt gets longer as you pass more passages, so a bigger k costs twice. Always do this arithmetic at the **tail**. p95 rerank latency on a shared GPU includes queueing behind other requests, and queueing is precisely where the distribution goes long. A model that averages 2ms per pair can sit at 8ms per pair at p95 under load. Sizing k from the mean produces a system that misses its budget exactly when it is busiest. ## Batching changes the shape of the curve The naive reading of "O(k) forward passes" is k sequential model calls. In practice you submit all k pairs as one batch. A GPU processes a batch of 50 pairs in far less than 50 times the cost of one, because the work is one large matrix computation instead of fifty small ones that leave the accelerator idle between launches. Up to the point where the batch saturates the device, added candidates are close to free; past it, latency turns linear again. The constraint on batch size is **activation memory**. Memory scales with batch size times sequence length, and attention activations scale worse than linearly in sequence length. A batch of 50 pairs at 512 tokens is routine on a mid-range inference GPU; the same 50 pairs at 2048 tokens may not fit, forcing the runtime to split into several batches and pushing latency back up. So the practical ceiling on k is usually set by memory at your chosen sequence length, not by an abstract time-per-pair. ## Sequence length is the underrated lever Because the query and the passage share one input, long chunks are expensive twice: they consume the sequence budget and they inflate attention cost. Halving passage length often saves more time than halving k, and it costs less ranking quality, provided the truncation does not chop off the part of the chunk that answers the question. This is one of the places where chunking strategy and reranking budget are the same decision. ## Model size and placement Smaller reranker checkpoints (base-sized rather than large) are several times faster and typically give up a modest amount of ranking quality. Quantization and distilled rerankers push further. Whether the model runs on a CPU pool or a GPU changes the arithmetic by an order of magnitude; on CPU, small rerankers at short sequence lengths are viable at low QPS but degrade sharply with k. ## Prove the depth is worth paying for More candidates is not monotonically better in practice. Beyond some depth the added candidates are mostly irrelevant, and a reranker that is imperfect on out-of-distribution text can promote one of them above a genuinely good hit. Run the sweep: score a labelled query set at k = 10, 25, 50, 100 and plot ranking quality against measured p95 latency. Very often the curve flattens well before the latency budget does, and you take the cheaper point. ## Degradation, not failure Design for the moment the budget is blown. Sensible fallbacks are a timeout on the rerank call that returns first-stage order, a shrunken k under load shedding, and separate budgets for interactive versus batch traffic. Silently waiting on a saturated GPU is the worst option, because the reranker's contribution — a better ordering — is worth far less to the user than a timely answer.