Scheduling Autonomous Agents With Heterogeneous Tool Latencies

Autonomous agents don't run like the request-response workloads that LLM serving engines were built for, and the gap between the two is why so many production agent deployments feel sluggish no matter how much GPU capacity gets thrown at them. Scheduling has to become runtime-adaptive, because the fixed, blanket assignments inherited from conventional cloud infrastructure fail in specific, repeatable ways once tool calls, variable-length contexts, and mixed CPU-GPU execution enter the picture.

Agent deployments feel slow even with spare GPU capacity because serving engines like vLLM, Orca, and TGI were tuned for single-turn request-response workloads, not the pause-and-resume pattern that agent sessions produce. A single session may call a search API, wait on a database query, invoke a code interpreter, and return to the model several times before finishing, and each of those pauses forces the scheduler to decide whether to hold KV state in memory or evict it and pay full prefix recomputation on resumption. Compounding that, 4 seconds of latency accumulate across a five-step pipeline before a user sees any output, and maximizing raw GPU token throughput, which is what most serving engines still optimize for, does nothing to address that. Redesigning scheduling for these sessions requires four capabilities working together: unified telemetry across GPU and CPU execution, decoupled admission and execution decisions, predictors that read prompt semantics rather than token counts alone, and per-session conditional KV retention based on whether warm resumption actually shortens the end-to-end critical path.

Serving engines like vLLM, Orca, and TGI were tuned for a world where a request comes in, the model generates tokens, and the session ends. Agent harnesses don't work that way. A single agent session might call a search API, wait on a database query, invoke a code interpreter, then come back to the model for another round of reasoning, potentially many times before the task finishes. That pause-and-resume pattern breaks assumptions baked deep into how GPU schedulers decide what to run next.

Profiling work across 19 common AI tools, sorted by whether they run faster on GPU or CPU, found 11 are GPU-preferred, 4 sit in ambiguous territory, 3 are effectively device-neutral, and 1 actually ru... Profiling work across 19 common AI tools, sorted by whether they run faster on GPU or CPU, found 11 are GPU-preferred, 4 sit in ambiguous territory, 3 are effectively device-neutral, and 1 actually runs better on CPU because PCIe transfer overhead eats any GPU advantage. Default to GPU-first placement for everything, which is what most agent frameworks do without thinking about it, and a meaningful chunk of tool calls end up on the wrong device before the session even starts.

Simple load-balancing tricks such as round robin, random assignment, or power-of-two-choices work fine in classic serving because requests are short and arrive at high volume: a bad placement decision gets amortized across thousands of similar requests within seconds. Agent workloads remove that safety net. A single session through an agent harness can run substantially longer than a conventional inference request, so one bad scheduling call doesn't wash out. It sits there, blocking other work, for the full duration of the session.

Why do agent deployments feel slow even with plenty of GPU capacity?

Two structural shifts explain why the old scheduling playbook stopped working, and both need to be understood on their own before any fix makes sense.

The first is temporal. Serving used to mean single-turn inference: prompt in, tokens out, done. Agent sessions stretch that into multi-turn execution, where the session lifetime is no longer bounded by one generation pass. KV cache, which used to be short-lived scratch space that got discarded almost as soon as it was created, becomes persistent execution state that has to survive across tool-wait phases. Every time a session pauses to run a tool, the engine faces a real decision: hold onto the KV state so the session can resume fast, or evict it and eat the cost of recomputing the prefix when the model comes back online. Get that decision wrong, in either direction, and latency stacks up.

The second is spatial. Each session's footprint expands, both in what it feeds the model and in what infrastructure has to serve it. On the input side, workloads move from chat-scale prompts of a few hundred tokens to repository-scale contexts carrying accumulated conversation history, tool traces, and execution logs. On the execution side, serving stops being a GPU-only problem, since tool invocations frequently run on the same host's CPUs. GPU inference and CPU tool execution are now coupled on the same critical path.

The latency math here is not abstract. A system prompt running several thousand tokens, combined with tool definitions and retrieved context, can push prefill past 9,000 tokens before the model produces a single output token. That pairing with an 800-millisecond time-to-first-token means a five-step agentic pipeline burns roughly 4 seconds before the user sees anything useful, accumulated across the TTFT of each step. Maximizing raw GPU token throughput, which is what most serving engines are still tuned to do, stops being the right objective. The engine has to optimize for end-to-end workflow completion, under pressure that spans GPU compute, KV cache capacity, and host CPU availability all at once.

Three specific failure modes that emerge from these shifts

These two shifts don't stay separate in production. These two shifts combine into three failure modes that appear over and over in agent serving logs.

The first is the KV-cache trap. Holding KV state through a tool-wait phase means the session resumes fast, without rebuilding its prefix from scratch. But hold too much state, across too many concurrent sessions, and memory gets stranded: fewer new sessions can be admitted, and everyone waiting in line suffers head-of-line blocking. Evicting too aggressively causes the opposite failure, a cold restart that pays full prefix recomputation on every resumption. No fixed policy threads this needle, because the right call depends on how long the specific tool call actually takes, and that duration varies wildly from one tool to the next.

The second is head-of-line blocking on the queue itself. A repository-scale prefill sitting at the front of the batch can stall short, cheap continuations that arrive right behind it. Batching heterogeneous-length requests together without accounting for this makes both tail latency and overall task completion time worse. Some systems have been built around this exact problem by treating agent programs as first-class citizens rather than treating each LLM call as an isolated event, introducing program-level context into the scheduling layer.

The third failure mode is unpredictable tool-call latency. When an agent calls an external API or a structured data source, the actual computation happens somewhere else, so local GPU and CPU usage during the call stays low. That looks harmless from a resource-monitoring standpoint, but the wall-clock duration of that call can span orders of magnitude depending on what's being called: the wall-clock duration of that call can vary enormously depending on what's being called. A scheduler with no way to anticipate that duration can't make a rational call about admission or KV eviction, because it's guessing blind.

These three failures compound rather than staying isolated. A long tool wait triggers KV eviction, the eviction forces a cold-start prefill on resumption, and that cold-start prefill then sits at the head of the queue blocking every other session behind it. One bad decision propagates latency across the entire concurrent workload.

What runtime-adaptive scheduling requires

Fixing this needs four capabilities working together, not one clever trick.

Holistic visibility comes first: the scheduler needs a single, unified telemetry stream covering both GPU inference stages and CPU tool-execution stages at once. Monitoring them in separate silos, the way most infrastructure does by default, means the scheduler is always reasoning about half the picture.

Admission and execution decisions have to be decoupled. Whether to admit a new session onto the system is a different question from how to execute the session already running, and collapsing the two into one policy causes heterogeneous resources, GPU memory, CPU cycles, KV cache slots, to get oversubscribed simultaneously.

Inference time and the structure of downstream model calls both depend on what's actually in the prompt, not just how many tokens it contains, so the scheduler needs predictors that read prompt conten... Inference time and the structure of downstream model calls both depend on what's actually in the prompt, not just how many tokens it contains, so the scheduler needs predictors that read prompt content alongside device state and runtime features.

And KV retention has to become conditional rather than policy-driven: retain state only when the math shows that warm resumption strictly shortens the end-to-end critical path for that specific session, calculated per session rather than applied as a blanket rule.

That rules out average-value estimation, which ignores prompt semantics and leaves the scheduler blind to the variance that actually matters, and it rules out single-agent, single-workload designs such as ORION, Pie, and Parrot, none of which were built to generalize across many concurrent, heterogeneous sessions running at once.

Classical operating system abstractions, processes, threads, files, sockets, resource controllers, were built for workloads that don't shift shape at runtime, which is analogous to the situation here. Agent workloads are dynamic and semantica... Classical operating system abstractions, processes, threads, files, sockets, resource controllers, were built for workloads that don't shift shape at runtime. Agent workloads are dynamic and semantically rich in a way those abstractions never anticipated, and the scheduling layer is where that mismatch costs the most in practice.

MARS: co-scheduling GPU inference and CPU tool execution as a unified problem

MARS, short for "Efficient, Adaptive Co-Scheduling for Heterogeneous Agentic Systems," treats GPU inference and CPU tool execution as one scheduling problem rather than two separate ones bolted together.

The design splits into two layers. An external control plane establishes that unified visibility across both GPU and CPU execution through a single information stream, and it keeps admission decisions separate from execution decisions specifically to stop heterogeneous resources from getting oversubscribed at the same time. Underneath that, an internal agent-centric scheduler prioritizes latency-sensitive continuations, resolves the head-of-line blocking described above, and retains KV cache only when doing so provably shortens the end-to-end path for that session. Both layers work off live telemetry, current system state.

The results back up the design. MARS cuts end-to-end latency by up to 5.94x while holding system throughput close to its maximum. It's also been integrated as the serving backend for OpenHands, the open-source coding-agent framework, where on an H200 deployment it improved task completion time by up to 1.87x. Notably, MARS was built by extending vLLM rather than replacing it, which says something practical: purpose-built agent scheduling doesn't require throwing out existing serving infrastructure, it can be layered on top of it.

SwarmX: using neural predictors to make tail-latency decisions before the request runs

SwarmX, "Agentic Scheduling for Low-Latency Agentic Systems," starts from a different piece of the same problem: since both inference time and the structure of model calls depend on prompt semantics, a scheduler that only looks at request metadata, token count, arrival time, is working with the wrong inputs.

SwarmX's answer is a set of scheduling-specific neural predictors that take in prompt semantics alongside device state, runtime conditions, and features specific to the target model. Rather than handing routers and autoscalers a single point estimate, latency will be X milliseconds, it exposes full distributional predictions, so downstream systems can make decisions aware of the tail, not just the average case. The framework also builds in mechanisms for training these predictors and adapting them online, which matters because a predictor trained once on a fixed workload distribution goes stale the moment traffic patterns shift. All of it plugs into a scheduler-agent framework meant to sit as a common layer underneath existing scheduling and model-serving stacks rather than replacing them.

Production deployment spans nearly 1,000 GPUs and roughly 1,000,000 CPU cores, with controlled experiments run separately on a 128-GPU testbed. That's not a lab toy, it's infrastructure tested at a size where scheduling mistakes are expensive.

The agentic CPU–GPU scheduler: reaching optimal device mapping without offline training

A separate line of work asks a narrower question: can an LLM agent figure out the right CPU-GPU device mapping for a workload without any offline training?

The design pairs an LLM agent with an algorithmic runtime monitor. The monitor's job is to expand what the agent can actually observe, using running averages, symmetric reprobing, swap reprobing, and exploration hints, so the agent isn't reasoning over a thin slice of telemetry. Critically, the monitor never tells the agent which mapping to pick. It only enriches what the agent sees; the agent still has to reason its way to the decision. And the whole system requires zero offline training, which matters because offline-trained schedulers are only as good as the workload distribution they were trained on.

Tested across 13 scenarios covering serial execution, parallel contention, and memory-constrained execution, this agent-plus-monitor setup reached the brute-force optimal device mapping in all 13 cases. It matched the best classical baseline on mapping accuracy and outperformed HEFT, StarPU, and a naive all-GPU policy across the board. For a method with no training phase, that's a strong result, and it suggests LLM agents can substitute for hand-tuned heuristics in device-mapping decisions specifically, where the search space is small enough for an agent to reason over directly.

When LLM agents as schedulers earn their cost

Not every scheduling problem benefits from putting an LLM in the loop, and a study on deadline-aware, mixed-criticality task scheduling at the autonomous-vehicle edge draws that line clearly.

The setup: deadline-aware scheduling across heterogeneous mobile edge computing servers, handling autonomous-vehicle perception offloading, where task criticality varies and deadlines are hard constraints. The comparison pits a strong windowed contract-net heuristic against the same heuristic with an LLM control plane layered on top.

Under stationary load, meaning traffic that doesn't shift in character over time, the LLM control plane adds nothing. The heuristic alone hits a task-completion rate of 0.902, ahead of all 15 other baselines tested, at 0.87 of the CP-SAT solver's theoretical upper bound. Adding an LLM on top of an already near-optimal policy just adds latency without moving the needle on outcomes.

The picture flips once the workload stops being stationary. When a mid-run surge of safety-critical tasks hits the system, non-stationary conditions the static heuristic wasn't built to react to, the LLM control plane pulls ahead significantly, beating both the fixed heuristic and a bandit-based baseline. The heuristic can't adapt its policy mid-run; the bandit adapts too slowly to react within the surge window. The LLM control plane earns its cost exactly where conditions change faster than a fixed policy can track, and not one moment before that.

Multi-agent negotiation as a scheduling primitive for distributed edge deployments

The device-mapping and edge-scheduling results above share a common thread: single-agent reasoning, paired with the right observability, already handles a surprising share of scheduling decisions without training data. Scheduling has to span multiple independent agents, each with a partial view of a distributed edge deployment, none of them holding the full picture on their own.

That's a different problem from co-scheduling GPU inference and CPU tool execution within one system. It's closer to negotiation: multiple agents, each responsible for a slice of infrastructure, need to agree on task placement and resource allocation without a central scheduler that sees everything at once. Contract-net style protocols, the same family of idea underlying the windowed heuristic in the autonomous-vehicle study, point toward one path, where agents bid on tasks and negotiate handoffs rather than waiting for instructions from a single controller. Whether that negotiation should run through fixed protocols or through LLM agents reasoning over each other's bids is still an open design question, and the honest answer is that the field hasn't settled it yet.