Do LLM Serving Schedulers Survive Agent Workloads?

Systems that serve large language models are tuned and compared on recorded prompt traces: streams of independent chat requests replayed at fixed timestamps. More and more of the traffic these systems carry now comes from software agents. An agent is a program that calls the model, runs a tool, reads the result, and calls the model again, often for dozens of turns. Some agents also split one job across an orchestrator and several sub-agents. Agent requests are not independent. Each one waits on the previous answer and on a tool run, sessions share long and growing prompts, and failing sessions loop for many turns. This proposal asks a plain question. If you rank serving schedulers on chat-style traces and then rank them again on live multi-agent software-engineering runs on real GPUs and real code sandboxes, do the rankings agree? We expect they do not, and that the disagreement can be repaired cheaply.

The work has two halves. The first is an evaluation ladder that runs the same scheduling policies under three conditions on identical hardware: classic open-loop trace replay, dependency-preserving replay of recorded agent runs, and live closed-loop agent execution. The second is a two-level scheduler that treats each agent job's tree of model calls as the unit of placement and migration, rather than individual requests. If replay that preserves dependencies reproduces the live rankings, the community gets a cheap and reproducible benchmark for agent-era serving. If only live runs do, that is direct evidence of a reality gap in how this whole line of systems is evaluated.

Core Claim

Two-level serving schedulers are evaluated on open-loop chat traces. The global layer decides which machine handles which request, and a local layer orders work on each machine. Llumnix uses ShareGPT, BurstGPT and synthetic power-law arrivals. HexGen-3 uses WildGPT, OpenThoughts and math traces inside a simulator that, by its authors' own account, assumes deterministic hardware and ignores jitter. Our claim is that the per-request metrics these papers optimize, first-token latency and time between tokens, are poor predictors of what matters for agent workloads. The metric that matters there is how long a whole agent task takes from issue to final patch, and how many tasks finish within a wall-clock budget.

The mechanism is structural. An agent's calls form a dependency tree, and the task finishes only when the slowest branch finishes. Placement decisions that are good for independent requests can therefore be bad for trees. Spreading one session's calls across instances destroys reuse of the cached prompt prefix and pays transfer costs on every hop. That is the situation analyzed by Afrati et al., who show that under large communication delays one should move whole subtrees between processors rather than individual tasks, and that with very large delays serial execution on one processor is optimal. We borrow that insight as a design principle. We do not borrow it as a theorem, since their result is for two identical processors and unit tasks.

Research Program

The first component is a modular harness. Agent workload generators, serving backends, scheduling policies, and sandbox executors sit behind fixed interfaces, so that any policy can be run under any workload tier without code changes. This is the same separation OmniEvaluator uses to decouple inference backends from evaluation suites, applied here to scheduling experiments.

We use three workload generators chosen because they produce very different call-tree shapes on the same tasks:

  • A fixed procedural pipeline in the style of Agentless: localization, repair, then validation. This gives a short, shallow, predictable tree.
  • A single long-horizon agent in the style of SWE-agent. This is a deep linear chain. That paper reports that successes are fast and failures are slow, with failing runs exhausting many turns.
  • An orchestrator with two sub-agents, following the hierarchy BOAD found to be optimal. BOAD saw performance degrade beyond two sub-agents. This gives fan-out with joins.

All three run against open-weight models we serve ourselves. We use BOAD's 36B Seed-OSS class model and the Qwen3-30B-A3B model used in HexGen-3's evaluation. Tasks come from SWE-bench-Verified and SWE-bench-Live, with real repository containers and real test execution.

The ladder has three tiers, all on the same physical cluster:

  • Tier 1 (open-loop chat replay). The protocol used by Llumnix and HexGen-3.
  • Tier 2 (dependency-preserving replay). We record full agent runs as call trees. Each record keeps prompt lengths, output lengths, shared-prefix structure, and measured tool and sandbox durations. We then replay them so that a call is issued only after its parents finish plus the recorded tool delay. Serving latency therefore propagates into task time, but the agent's decisions are frozen.
  • Tier 3 (live closed-loop runs). The model actually generates and tools actually run. Latency can now change outcomes, through wall-clock budgets and timeouts, and the real noise sources are present: container start-up, filesystem contention, multi-tenant interference. Real sandbox launch cost cannot be ignored. The GNU Parallel study on Frontier measured container runtimes ranging from over 5,200 launches per second (Shifter) down to about 65 per second (Podman-HPC).

The second component is the tree-aware scheduler, which has two levels:

  • Global level. When a task arrives, it is assigned as a whole to one serving instance. The assignment is chosen by expected tree size and current load. Migration happens only at subtree granularity, for example moving a sub-agent's entire future session together with its cached prefix, and is triggered by imbalance. This reuses Llumnix-style live cache migration as the transport.
  • Local level. Within an instance, requests are ordered by how much of their task's remaining critical path they sit on. This is estimated online from the task's turn count and tree shape. The local level also applies an explicit policy for long-running sessions. Because failing runs are the long ones, the scheduler can deprioritize sessions past a turn threshold so they do not starve fresh tasks. This is a deliberate outcome-affecting choice, and we measure it as such.

Baselines

The naive reference is a least-loaded router with first-come-first-served local queues. Every agent call is treated as an independent request. This is what one gets by pointing an agent framework at a stock multi-instance deployment.

The strongest existing method is Llumnix, run with its global load balancing and live migration enabled. It is the most direct competitor: it is a two-level scheduler with request migration, and its authors report P99 first-token latency reduced by up to 15x on ShareGPT/BurstGPT traces. That is a per-request metric on open-loop traces, which is precisely the regime whose transfer we question. HexGen-3 is relevant, but its disaggregated design and simulator-driven allocation make it a hardware-allocation competitor more than a request-placement one. We include its global/local split only as a configuration variant where the hardware allows.

The simpler competitor a practitioner would actually deploy is session-sticky routing with prefix caching. Every call from a session goes to the instance holding its prefix, and nothing else changes. This isolates whether our gains are just "keep the cache warm."

Two ablations isolate the proposal's ingredients:

  • Tree placement without critical-path ordering. This separates the global-level idea from the local-level one.
  • Per-request migration instead of subtree migration, with everything else held fixed. This tests the Afrati-inspired claim directly.

Fairness is enforced by construction. All policies run on the same GPUs, the same model weights, the same task subsets, and the same sampling temperature and agent seeds. Each policy gets the same tuning budget, a fixed number of configuration trials on a held-out SWE-bench-Verified slice. Each live configuration is repeated over several seeds, because agent runs are stochastic.

Beating Llumnix means three things at equal hardware and equal tuning:

  • a statistically significant reduction in P90 task completion time on live tier-3 runs, for at least two of the three workload shapes;
  • no loss in resolution rate under an uncapped budget;
  • a higher resolution rate under a fixed wall-clock budget.

Beating sticky routing means the same improvement survives against it, especially on the fan-out workload.

For accuracy context, the workloads have reported resolution rates on Lacuna: BOAD 53.2% on SWE-bench-Verified and 20.0% on SWE-bench-Live, and Agentless 32.00% on SWE-bench Lite. No reported result was found on Lacuna for any serving scheduler measured on agentic workloads.

Why not just…?

Why not just use session-sticky routing with prefix caching? This is the real threat. It may capture most of the benefit for linear single-agent chains, where a session is one path and stickiness already keeps it local. It has no notion of a task's critical path, though. Under fan-out it either piles all sub-agents onto one hot instance or splits them blindly. It also never moves a session once it is placed. The sticky-routing baseline and the per-shape breakdown settle this. If sticky routing matches our scheduler on all three workload shapes, the scheduler contribution collapses. We would then report that, and the evaluation ladder becomes the paper's main contribution.

Why not just replay recorded agent traces with their original timestamps? That is what tier 1 effectively does for agent traffic. It breaks causality: a slow response no longer delays the follow-up call, so queueing effects compound incorrectly and task completion time cannot even be computed. Tier 2 is the minimal fix. Whether tier 2 is enough is one of our decisive measurements, not an assumption.

Why not just use a procedural pipeline like Agentless and avoid the scheduling problem? Agentless reports 32.00% on SWE-bench Lite at $0.70 per issue, so cheap fixed pipelines are competitive. But USEagent reports that dynamic workflows beat static ones by 4% to 33%, and BOAD reports a 63% gain from hierarchy on SWE-bench-Live. Hierarchical and long-horizon workloads are therefore real traffic that needs serving. We include the Agentless-style pipeline as one workload precisely to show where scheduling matters little.

Why not just improve the simulator, as HexGen-3 would? A better simulator is a reasonable end goal. However, one cannot know which missing effects matter without first measuring against real execution. Tier 3 provides that ground truth, and the tier-1/2/3 gaps tell a simulator builder what to model.

Proposed Experiments

The first decisive check measures rank agreement. We rank roughly six policies (the baselines, our scheduler, and its ablations) by the headline metric of each tier, and compute Kendall's tau between tiers 1 and 3 and between tiers 2 and 3. We pre-commit to an interpretation. If tier-1 rankings agree strongly with tier-3 rankings, the reality-gap claim is false and we say so. If tier 2 agrees with tier 3 and tier 1 does not, we release the recorded call trees and replayer as the reproducible benchmark. If neither replay tier agrees, outcome feedback through budgets is doing the damage. We confirm or rule this out by rerunning tier 3 with budgets removed.

The second check decomposes the gap. We add noise sources to tier 2 one at a time and see which ones move the ranking toward tier 3: real sandbox launch latency, filesystem contention, and multi-tenant interference.

The third check evaluates the scheduler on the metrics defined above (P90 and P99 task completion time, tasks per GPU-hour, and resolution rate at fixed wall-clock budgets) on SWE-bench-Verified and SWE-bench-Live. We also report the per-request first-token and between-token latencies, to show directly when request-level wins and task-level wins diverge.

A final check targets the long-session policy. Deprioritizing long sessions should raise budgeted throughput, because SWE-agent finds that long runs are disproportionately failures. It could also cut off late successes. We report both effects separately, so the policy is never credited with gains that are really lost solutions elsewhere.