Search Latency: Where the Milliseconds Go
6 min read · updated August 3, 2026
You cannot optimise a latency you have not divided up. A budget allocated in advance turns “search is slow” into a statement about which line overran, and it is the only artefact that makes the conversation about a fix rather than about a feeling.
A budget, not a measurement
Start from a target rather than from a profile. Take 200 ms at p95, server-side, for a full search page. Every number below is an allocation — a decision about what each stage is allowed to spend, not a claim about what any particular system does.
| Stage | Description |
|---|---|
| query understanding — 10 ms | Normalisation, spelling, parse, cache lookups. Small, but a synchronous model call here would blow the entire budget on its own, which is the argument for precomputing rewrites for the head of the distribution. |
| candidate generation — 40 ms | Inverted index, ANN index, or both in parallel and fused. Grows with corpus size, with candidate count, and with the number of shards it fans out to. |
| feature hydration — 25 ms | Fetching the features the ranker needs for a thousand candidates: popularity, price, stock, freshness. Usually the most underestimated line in the table, because it is a fan-out to a key-value store rather than a computation. |
| ranking model — 15 ms | A gradient-boosted ensemble over a thousand candidates. Cheap, predictable, and rarely the problem. |
| reranking — 60 ms | A cross-encoder over the top tens. The largest single line, and the one most directly under your control, because it scales linearly in the number of documents you choose to send it. |
| snippet generation — 30 ms | Fetching document text and highlighting. Frequently a second network round trip to a document store, and frequently the surprise in a profile. |
| facet counts — 15 ms | Cardinality over the full result set per facet value. Bitmap intersections, discussed in the faceted search page. |
| serialisation and transport — 5 ms | Assembling the response. Small unless the payload is large, which it becomes when somebody adds full document bodies to it. |
That sums to exactly 200 ms with no slack, which is the point of writing it down: it is immediately obvious that any stage overrunning means another must be cut. The value of the exercise is not the numbers — yours will differ — it is that the argument about the reranker becomes an argument about which 60 ms it is spending, rather than about whether reranking is worth it in the abstract.
What each line is actually doing
Three of the lines have properties worth knowing before you try to move them.
Reranking scales linearly and only linearly. If the cross-encoder handles a documents per second, reranking k2 documents costs k2 / a seconds. Halving k2 halves the line. Nothing else in the pipeline offers a lever that direct, which is why it is the first place to look and why the choice of k2 deserves the sweep described in retrieve, rank, rerank.
Feature hydration is a fan-out in disguise. Fetching twenty features for a thousand candidates is twenty thousand lookups. Batched into one round trip it is one network hop; done naively it is twenty thousand, and it will be the entire budget. This line is usually fixed by batching and colocation rather than by making anything faster.
ANN search trades recall for time explicitly. Vector indexes expose a search-effort parameter — ef in an HNSW implementation — that buys recall with latency along a curve you can plot. That makes it one of the few lines with a real dial rather than a rewrite. The mechanism is in the HNSW page; what belongs here is that the dial exists and that the right setting is a budget decision, not a default.
Fan-out amplifies the tail
Here is the effect that makes distributed search feel slower than its components. A query that fans out to n shards is not finished until the slowest shard replies. If each shard independently exceeds some threshold with probability q:
P(at least one shard is slow) = 1 - (1 - q)^n q = 0.01 (each shard's p99), n = 20 shards 1 - 0.99^20 = 1 - 0.8179 = 0.182
Eighteen percent of queries touch a shard that is in its own slowest one percent. So the p99 of the whole query is set by something much further out in each shard’s distribution. Turn it around and ask what per-shard reliability a 20-shard p99 requires:
want 1 - (1 - q)^20 = 0.01
(1 - q)^20 = 0.99
1 - q = 0.99^(1/20) = 0.99950
q = 0.00050
Each shard must hold the latency at its p99.95, not its p99.This is the argument Dean and Barroso made in “The Tail at Scale” (CACM, 2013), and it is the reason tail latency in a fanned-out system is a systems problem rather than a per-component optimisation. Their mitigations are the ones still in use: hedged requests, where a duplicate is sent to another replica once the first has exceeded the p95 and the loser is cancelled, which costs a few percent of extra load and removes most of the tail; tied requests, where both replicas know about each other and the second cancels itself; and micro-partitioning so that a slow shard can be moved rather than waited on.
The general principle, which is worth carrying beyond search: at fan-out scale, the tail of a component becomes the median of the system. The same reasoning applied to model serving is in latency percentiles for LLM calls.
The levers, in order of size
- Rerank fewer documents. Linear, immediate, and the quality cost is measurable rather than assumed. Sweep
k2against nDCG and find where the curve flattens; the documents past that point were costing latency for nothing. - Cache the head. Half the volume is in a thousand queries, by the Zipf derivation in the long-tail page. A result cache keyed on the normalised query plus the filter set plus, where relevant, the permission set, serves that half from memory. It is the cheapest large win available and the only reason to avoid it is a personalised ranking, which makes the key too specific to hit.
- Compute facets and snippets in parallel with ranking, not after it. They depend on the result set, but so does nothing else, and running them concurrently removes 45 ms of the budget above from the critical path.
- Hedge instead of over-provisioning. The tail arithmetic says a second request after the p95 is cheap and effective. Adding capacity to fix a tail caused by fan-out is expensive and mostly does not.
- Stream what you have. Results first, facets and counts second. This does not change any number in the budget and it changes what the user experiences, which is the number that was actually the target.