Improving tail latency in parallel LLM calls

Our AI agents at HOAi search a community association’s documents. Postgres retrieves candidate pages; model calls filter them for relevance and summarize the ones that pass.

In our previous post, we fixed the Postgres retrieval plan. Searches still occasionally took 30 seconds or more. The remaining problem came from a design choice meant to make them fast: we ran the model calls in parallel.

The slowest batch sets the latency #

We split candidate pages into batches of five and run every batch concurrently. The phase finishes only when its slowest batch does.

In one 113-second trace, most of the 21 batches finished in two to seven seconds. One took 79 seconds. That request set the reranking latency.

The same pattern appears across production searches on GPT-4.1-mini priority:

At p95, 79 candidates create about 16 chances for one provider stall.

Race each batch #

We moved reranking from one GPT-4.1-mini priority request to two GPT-5.4-mini default-tier requests. Each batch launches both, takes the first successful result, and aborts the loser. It’s sending every request twice, applied per batch.

We also moved summarization from GPT-4.1-mini priority to GPT-5.4-mini priority. The latency table above is the old baseline; we do not yet have enough post-rollout data to publish a new p95.

What it costs #

We priced the same production token mix under the old and new configurations. Each column summarizes the costs of individually priced calls or searches:

The reranking bounds differ in how much output we charge to the aborted request. Cached-input discounts and partial usage from aborted requests may change the realized cost.

The takeaway #

When a search waits for many parallel LLM calls, one straggler sets the latency. Racing each batch cuts that tail for roughly twice the cost.