Retrieval Latency Budgets in Multi-Step Agentic Workflows

Retrieval latency in an agentic system is never one number. It's a chain of numbers, embedding, search, reranking, assembly, each with its own budget, and the chain only holds together if every link gets sized correctly. Most teams profile the wrong thing: they measure total response time, see the LLM call eating the biggest slice, and spend a quarter optimizing inference while retrieval sits there unexamined, quietly adding 300 or 400 milliseconds nobody accounted for. That's the mistake this piece is about, and it's a costly one once an agent starts calling retrieval more than once per turn.

Retrieval breaks into four stages: turning the query into a vector, searching for neighbors, reranking the candidates, and assembling the result into something the model can use. Each has a distinct latency profile, and a fast number in one stage means nothing if a slow number sits upstream. Supermemory's May 2026 writeup shows a vector search running under 50 milliseconds is a real engineering win, but if the embedding call in front of it takes 300 milliseconds, the user never feels the fast part. The fast stage is invisible inside the slow one. Stage-by-stage budgeting reveals where latency actually accumulates, while a single end-to-end target hides which stage is responsible.

Multi-step agents make the problem worse, not better. A planner agent, a retrieval agent, a tool agent, a validation agent, each one might run its own retrieval sub-chain, and because these steps depend on each other sequentially, the latency adds up rather than averaging out (per medium.com/@vinodkrane). Agentic RAG compounds this again: unlike classic RAG's one retrieve-then-generate pass, an agentic system can call the retriever repeatedly within a single user turn, rewriting the query and switching tools between hops. And because context grows with every hop, token count becomes its own latency tax. By step ten of an agent loop, the model may be chewing through something like 80,000 tokens just to decide its next move, and every one of those tokens lengthens inference time (per medium.com/@vinodkrane). Treating the retrieval budget as one lump sum produces unpredictable p95 spikes with no clear cause. Break it into stages and the spikes become traceable.

How the agent type sets the total response target from which retrieval must be carved

Voice AI agents live inside roughly an 800 millisecond total response window, and speech synthesis plus end-of-turn detection eat most of that, leaving retrieval under 100 milliseconds (per supermemory.ai). A number that's generous for one interaction type is disqualifying for another.

Conversational chat agents get more room, with a retrieval ceiling around 200 milliseconds before the experience starts to feel sluggish; users tend to notice delays past roughly 200 milliseconds as unnatural, and the 200ms retrieval figure specifically comes from supermemory.ai's analysis. Streaming answers complicate the picture further: when output streams token by token, time to first token is what the user actually feels, and that clock runs differently from the one the system logs internally (per supermemory.ai). Enterprise copilots can stretch retrieval to around 400 milliseconds inside a 3-second window, since users expect a bit of thinking time from something doing real work. This is a planning allocation, not a measured benchmark or a promise any vendor makes, and it excludes answer generation.

That table changes what "fast enough" even means. A 150 millisecond reranker is a rounding error for an enterprise copilot and a dealbreaker for a voice agent. Sub-50 millisecond similarity search across millions of embeddings is achievable today (per supermemory.ai), and Qdrant has been reported to deliver 6 millisecond p50 latency with native hybrid search support. Treating the retrieval budget as one lump sum produces unpredictable p95 spikes with no clear cause. The order of operations matters here: define the target for the specific interaction first, then work backward into what retrieval is allowed to cost. Doing it the other way around, measuring what retrieval happens to take and hoping it fits, is how teams end up with SLA breaches they can't explain.

Allocating the retrieval budget stage by stage: embedding, search, reranking, assembly

Supermemory's May 2026 writeup offers an illustrative split for a 500 millisecond retrieval allowance: 50 milliseconds for network and edge overhead, 80 for orchestration, 120 for primary retrieval, 100 for reranking and assembly, and 150 held back as headroom. This is a planning allocation, not a measured benchmark or a promise any vendor makes, and it leaves answer generation out of the calculation. Calling it a complete agent-response budget would be misleading. But as a template for how to think about the split, it's useful.

Start with query encoding, the stage most teams forget exists. Precomputing document embeddings ahead of time is standard practice and it helps, but it does nothing for the query itself. Every new semantic search still needs a fresh embedding call, and unless there's an exact cache hit or a reusable query embedding, that call happens on the clock, every time (per supermemory.ai). It's also worth resisting the instinct to reach for the biggest embedding model available. A heavier model costs more latency, and that cost doesn't automatically buy better retrieval quality on a given corpus, it depends on the data.

Vector search itself is the stage where production systems have gotten genuinely fast. Sub-50 millisecond similarity search across millions of embeddings is achievable today (per supermemory.ai), and Qdrant has been reported to deliver 6 millisecond p50 latency with native hybrid search support. That number is a useful reference point, not proof that any one database is the fastest option for every workload; a benchmark only means something when it's matched on dataset, dimensions, filters, recall target, hardware, concurrency, and cache state, and vendors rarely publish all of those together.

Reranking is where things get expensive and where the payoff has to be weighed honestly. A cross-encoder reranker scores each candidate jointly against the query, which is more accurate than first-pass retrieval alone, but it's also the stage where retrieval latency tends to spike without warning. Feeding raw HTML into an LLM bloats the context badly; converting it to clean, structured Markdown can meaningfully reduce token consumption. But reranking isn't free lunch. If the candidate set coming out of vector search is already strong, adding a reranker on top can spend milliseconds without moving the answer quality at all, so it should be tested as an experiment rather than assumed as an upgrade (per supermemory.ai). This kind of architectural choice illustrates how the design of a memory module shapes where latency accumulates across the retrieval chain.

Assembly is the quiet lever most teams underweight. Model routing sends simple requests to smaller, faster models and reserves the heavy model for genuinely hard problems, cutting both latency and cost without giving up quality where it counts (per fiddler.ai). That's not just a cost optimization, it's a latency one, because fewer tokens at assembly means faster inference downstream. Here, "context quality over raw volume" is not just a slogan but something you can actually measure, because fewer tokens at assembly means faster inference downstream.

None of this works without headroom, and headroom isn't a nice-to-have buffer, it's a decision that has to be made in advance. A retry or timeout policy has to fit inside the overall deadline, and reserving 150 milliseconds doesn't guarantee a retry finishes in time. What happens when the deadline hits anyway, a partial answer, a clean failure, a delayed response, has to be decided before it happens in production, not discovered live (per supermemory.ai).

How to instrument a multi-step retrieval pipeline so you can see where the budget is going

Parallelism is real and it works, but only for tasks that are genuinely independent of each other. Multi-agent systems that decompose work into separate branches see meaningful latency reduction on embarrassingly parallel workloads (per arxiv.org/pdf/2507.08944). The catch is that most interesting agentic tasks aren't embarrassingly parallel. Complex reasoning tends to be step-by-step by nature, where each step needs the output of the one before it, which makes the whole chain unsuitable for parallel execution (per arxiv.org/pdf/2507.08944).

It gets harder still for agents that build their plan dynamically at runtime. You can't parallelize an execution graph you haven't computed yet, and if the agent is deciding its next action based on what just happened, there's no graph to optimize ahead of time (per arxiv.org/pdf/2507.08944). One emerging response to this is compile-time analysis: one approach uses a compiler that inspects the graph structure and automatically parallelizes whichever operations turn out to be independent, so the developer states intent and the compiler finds the fast path.

Short of that, a handful of practical techniques actually move the needle in sequential pipelines. Adaptive routing at the front of the pipeline separates cheap fact-lookup queries from expensive multi-hop ones before they ever reach the agent (Adaptive RAG, per dev.to/saaro_net, 2026). Semantic caching can serve somewhere between 60 and 90 percent of queries straight from cache, turning a few hundred milliseconds into tens of milliseconds (per fiddler.ai). Without span-level tracing, a p95 spike to 3 seconds tells nothing about where the time actually went, retrieval, inference, or orchestration all look identical from the outside (per fiddler.ai). Prefetching helps too, when the next step is predictable enough to start retrieval before it's explicitly requested, though it carries real risk: wasted calls, or worse, a wrong guess about what context will actually be needed (per supermemory.ai).

Parallelism itself isn't automatically a win. It can raise load and worsen tail latency, since orchestration overhead and contention over shared dependencies can eat the gains it was supposed to produce. Voice agents often cache embeddings aggressively, or skip reranking outright; these choices only make sense once the ceiling is written down explicitly rather than assumed.

There's no universal latency budget for retrieval, because the right ceiling depends entirely on what kind of agent is doing the asking (per supermemory.ai).

Without span-level tracing, a p95 spike to 3 seconds tells nothing about where the time actually went, retrieval, inference, or orchestration all look identical from the outside (per fiddler.ai). Fiddler's writeup points to a financial services firm running fraud detection agents at a million transactions a day as the kind of scale where this becomes existential rather than optional.

The minimum set of instrumentation points, per supermemory.ai's guidance: request start, retrieval start and end, model start, first output token, full completion, and every retry or error along the way, not just the successful runs. Tracking every retry or error, not just the successful runs, changes what the measured latency actually reflects. A system that appears faster because failed requests return early isn't actually faster, it's failing quietly and calling it speed.

Fiddler's July 2026 update names three metrics: Time to First Token, Output Tokens Per Second, and Time to Complete Response. Time to First Token surfaces cold starts and queue congestion. Output Tokens Per Second reveals inference compute limits. Time to Complete Response is the one users actually feel, and it's the number that should set timeout thresholds. Optimizing any one of these alone, while ignoring the other two, produces a metric that improves on a dashboard and does nothing for the person waiting on an answer.

OpenTelemetry spans across the pipeline, tagged with token counts, model selection decisions, and cache hit or miss ratios at each hop, let you correlate across services and find where things actually slow down (per fiddler.ai). At high trace volume, tail-based sampling keeps the overhead manageable while still preserving visibility into the slow requests that matter most.

Don't add each stage's p95 together and call the sum the end-to-end p95. Slow stages often land on different requests, or overlap in ways addition doesn't capture. The only way to get the real distribution is to trace complete requests end to end (per supermemory.ai). Ingestion latency, how long it takes to process a newly uploaded file, is separate from retrieval latency, how long a search takes over data that's already indexed. The first affects freshness, the second affects the user's actual wait time, and conflating them in a dashboard hides two different problems behind one number.

Guardrail checks deserve the same scrutiny. Running them inside your own environment keeps evaluation fast and avoids per-query costs from an external API that add up fast once volume climbs (per fiddler.ai). At meaningful throughput, an outside evaluation call on every query becomes both a latency tax and a cost problem at the same time.

The accuracy-latency tradeoff in memory and retrieval systems, and where it bites hardest

The only honest way to know is to measure the system as shipped, under real concurrency (per supermemory.ai). That's the tradeoff most teams accept as the cost of doing business: better memory, slower system. Dense vector databases and knowledge-graph traversal, both common in production memory systems, are named directly as sources of high retrieval latency in that same paper.

A newer system called Hippocampus (arXiv:2602.13594, February 2026) pushes back on the assumption that accuracy has to cost that much. It uses compact binary signatures for semantic search instead of dense vectors, paired with a structure called a Dynamic Wavelet Matrix that searches directly in the compressed domain, so the dense-vector and graph computation is skipped. The reported result is up to a 31 times reduction in end-to-end retrieval latency and up to a 14 times reduction in per-query token footprint, while holding accuracy steady on both the LoCoMo and LongMemEval benchmarks. It also scales linearly with memory size, which matters for agents that accumulate memory across many sessions over months rather than a single conversation.

The token footprint number deserves a second look, because it's not just a cost line item. A 14 times reduction in tokens per query means a shorter context fed into the LLM at each retrieval step, and shorter context means faster inference. Token efficiency and retrieval latency aren't two separate concerns here, they're coupled, and improving one improves the other automatically.

There's a failure mode that latency pressure tends to hide rather than cause. One documented production trace showed an agent retrieve several chunks, use most of them correctly, and then invent the remaining fact outright, with no faithfulness check and no judge gating the final answer before it shipped. The self-check step that would have caught it simply wasn't there. That's the argument for treating a faithfulness check as part of the retrieval budget rather than an optional extra bolted on later: skipping it to shave a few milliseconds off the response doesn't remove the risk, it just moves the failure downstream, into a compounding multi-step workflow where the wrong fact gets carried forward and treated as ground truth by every step after it.

How the web retrieval layer

fits into all of this comes down to the same principle that governs every other stage: latency has to be budgeted deliberately, not discovered after the fact. Pulling live information from the web, whether through search, page fetching, or crawling, adds another sequential hop in front of embedding and search, and it's often the least predictable one, since it depends on external services responding within a reasonable window. Timeouts and fallback behavior for that layer need the same explicit treatment given to reranking or assembly. If a web call doesn't return within its allotted slice, the agent needs a defined fallback, whether that's cached context, a narrower search, or a clear signal to the user that live data wasn't available, rather than an open-ended wait that blows through the whole response budget. The stage-by-stage discipline that governs embedding, search, reranking, and assembly doesn't stop at the edge of the retrieval index. It has to extend outward to anything the agent reaches for beyond its own stored data, or the whole budget built inward collapses the moment a single external call runs long.