Priority Queuing and Preemption in Multi-Job Agent Systems

Multi-agent systems fall apart at scale because the scheduler underneath them stops making sense, not because the models get worse. First-in-first-out queuing, the default in nearly every agent framework shipping today, works fine when a handful of agents run at a time. Pushing that to fifty or a hundred concurrent agents causes FIFO to start making decisions no one would sign off on if they saw them happening live: a report-generation agent hogging the queue for twenty minutes while a customer-facing chat request sits behind it, waiting for nothing in particular.

Most teams built their first agent, or their first three, in a world without collisions. One job ran, finished, and the next one started. Gartner's numbers suggest enterprise applications integrated with task-specific agents are set to jump from a small fraction in 2025 to a substantial share by the end of 2026, a world that is closing fast. Enterprise applications integrated with task-specific agents are set to jump from a small fraction in 2025 to a substantial share by the end of 2026, a compression of adoption that's outrunning the infrastructure meant to support it. That's a compression of adoption that's outrunning the infrastructure meant to support it.

FIFO's failures at scale come in a specific, repeatable pattern. Head-of-line blocking is the most visible: one long agent job parks itself at the front and every short, latency-sensitive request behind it just waits. There's no way to mark a job as urgent, so a critical task and a background one get treated identically. There's no floor under low-priority work either, so a heavy agent can eat almost all available capacity with nothing stopping it. None of this is being measured. Fairness that isn't tracked isn't fairness, it's luck.

Compound AI workloads make the failure sharper. A single agent task might chain together dozens or hundreds of LLM calls, each one wrapped around tool invocations, waiting on external APIs, and carrying KV cache state that either survives between steps or gets thrown away and recomputed. FIFO just sees a queue, not the LLM calls, tool invocations, external API waits, or KV cache state behind it. It just sees a queue.

None of this is a future risk. The AIOS project's own roadmap has listed priority-based scheduling as an open, unimplemented gap since May 2024. That's over two years of agent frameworks shipping into production without a solved answer to a basic question: whose work runs next, and why?

What priority queuing means in an agent context

The unit that gets scheduled in an agent system is the whole workflow. It's the whole workflow, a chain of dependent reasoning steps, tool calls, and observations that all belong to one task. Most GPU schedulers weren't built with that in mind. They treat each inference call as its own independent event and throw away whatever state connected it to the step before. SAGA, a paper appearing at HPDC '26, names this gap directly: scheduling at the request level instead of the program level, and pins it as the root cause behind latency inflation running 3 to 8 times higher than it needs to be in compound AI workloads.

Priority, in practice, is simple: rank an agent or a tenant as high, normal, or low, and let that rank steer who gets dispatched first when resources are tight. Fair-share weights do something related but distinct: they guarantee each agent a floor, a minimum slice of LLM capacity, so no single heavy consumer can starve everyone else out. Priority alone can't promise that. A low-priority job can sit at the bottom forever unless something intervenes.

That something is aging: a mechanism where a job's effective priority creeps upward the longer it waits, putting a hard ceiling on worst-case delay without anyone having to step in by hand.

AIOS makes a good case study for how far the industry actually is from any of this. Its SchedulerParams object already has a priority field. Every syscall has a set_priority() method sitting right there in the code. But there isn't a single call site for either one anywhere in the repository. The scheduling policy that actually runs is picked by an unrelated context-manager flag, not by anything resembling a named policy. The plumbing for priority exists. Nothing uses it.

Optimizing for fairness and low latency isn't free, and that tradeoff shapes everything downstream in this piece. SAGA quantifies the cost at roughly 30% lower peak throughput compared to a scheduler built purely to maximize batch throughput, a tradeoff dictated by its fairness and latency goals. That's a fair trade for interactive, latency-sensitive products. It's a bad trade for a batch pipeline that only cares about total jobs finished per hour.

The three main preemption mechanisms

Declaring priorities without a preemption policy is a wish list. Preemption is the enforcement mechanism: when something more urgent arrives, it takes resources away from a lower-priority job.

There are three main flavors, each suited to a different failure mode. Priority preemption lets a high-priority job bump a lower one on arrival, applied at the job level for gang-scheduled workloads and at the pod level for everything else. Quota reclamation preemption covers multi-tenant setups where spare capacity gets loaned out to opportunistic jobs; when the original owner needs that capacity back, it reclaims it through preemption. Backfill preemption works as a timeout-triggered safety valve: if a waiting job has been stuck too long because there simply isn't enough free capacity, it eventually forces its way in.

Preemption isn't free, though. Releasing and reallocating resources costs system overhead, and that cost can cascade: reshuffle one job and other allocations start moving too. Without aging or a hard floor, a low-priority job can get preempted over and over and never actually finish.

The sharpest version of this problem in LLM serving is the KV cache. Preempt an agent mid-inference without care, and its intermediate state gets evicted. Regenerating that state from scratch adds real latency, multiple times over, at every step where it happens. The preemption policy itself has to understand the workflow, not just the priority number attached to it.

Justitia takes the opposite bet. Given how expensive KV cache swapping is, it runs on a non-preemptive principle at the agent level: a request sitting in the waiting queue can never interrupt a running inference. Preemption only happens once an entire inference call finishes. That trades away some responsiveness (a high-priority job might wait slightly longer to interrupt) in exchange for cutting out the overhead of mid-flight cache eviction entirely.

Which approach fits depends on the shape of the workload: how long jobs typically run, and how painful KV cache eviction actually is in that specific deployment. There's no universal right answer here, only a right answer for the job mix in front of the operator.

SAGA's reframing of the scheduling unit as the whole workflow

SAGA's central claim, presented at HPDC '26 in Cleveland, is that scheduling individual inference requests is simply the wrong level of abstraction for compound AI work. The right unit is the entire workflow, the full program, because that's the only level where KV cache reuse, task dependency order, and fairness across tenants can actually be reasoned about together.

Three mechanisms carry that idea into practice. Agent Execution Graphs capture the structure of a workflow to predict where KV cache will get reused across tool-call boundaries, landing just a bit above Bélády's optimal offline caching policy, which is about as close to theoretically perfect as a live scheduler gets. Session-affinity batching with work stealing keeps correlated requests, ones sharing a prefix and KV state, sitting together on the same worker, while idle workers can still steal work to keep the cluster balanced overall. Agent Fair Share (AFS) measures fairness in terms of task completion time, with provable bounds on how far any tenant can deviate from its fair share, calculated at the workflow level rather than per call.

Run on a 64-GPU cluster serving SWE-bench coding agents alongside WebArena browser-navigation tasks, SAGA delivered roughly a two-thirds reduction in task completion time (geometric mean, statistically significant at p < 0.001) against vLLM v0.15.1 running prefix caching and affinity routing. GPU memory use improved by a solid margin. SLO attainment under multi-tenant interference hit 99.2%.

The cost, again, is roughly 30% lower peak throughput than a scheduler built purely to maximize batch efficiency. SAGA's authors treat that as an acceptable price for interactive deployments. Anyone running batch-heavy pipelines should weigh that number carefully before adopting the same approach. If agents in production are running multi-step reasoning chains with tool calls and outside API waits, request-level scheduling is quietly costing latency that workflow-aware scheduling can claw back.

Fairness across tenants under Justitia and SAGA's AFS without sacrificing completion time

Strict fair-share scheduling, where every tenant gets exactly its proportional slice at every moment, sounds fair on paper and slows everyone down in practice. Ignoring fairness entirely causes starvation instead. Neither extreme survives contact with a real multi-tenant deployment.

SAGA's answer is Adaptive Fair Scheduling. A global coordinator tracks an AFS score for every tenant and adjusts scheduling priority every 100 milliseconds. As a tenant's actual service falls behind its proportional share, its urgency score climbs, a self-correcting drift that pulls things back into balance without needing a human to intervene. AFS carries formal SLO guarantees under bounded contention, handing out capacity in proportion to each tenant's measured urgency. When preemption is needed, SAGA borrows Llumnix's migration mechanism: the preempted task's KV cache gets moved to a lower-priority worker rather than thrown away. Preempted work relocating rather than vanishing affects how quickly a preempted task can resume, since its KV cache moves to a lower-priority worker instead of being discarded. Preempted work doesn't vanish, it relocates.

Justitia solves for the same problem from a different angle, built around the fact that agents are task-parallel: one agent is usually made of several simultaneous inference requests, not a single call. Justitia's approach centers on measuring agent cost in memory terms, treating memory pressure as a primary scheduling constraint in LLM serving. It queues requests according to the overall demand of the agent each inference belongs to. Practically, that means every inference belonging to a high-priority agent runs back to back, without competing requests slipping in between them. And as covered earlier, Justitia's design stays non-preemptive within a single inference call: pending requests wait for the current one to finish rather than cutting in.

The name for this design is "selective pampering," and it captures something counterintuitive: serving agents in their fair completion order, saturated rather than throttled, is designed to improve overall throughput without systematically penalizing individual agents.

Putting the two side by side makes the contrast clean. AFS is preemptive, epoch-driven, and leans on cache migration to avoid wasting work. Justitia is non-preemptive, boundary-triggered, and leans on memory-centric cost modeling instead. The choice between them hinges on how much job lengths vary in a given deployment and on whether that deployment even has infrastructure for KV migration in place.

AIOS and AgentRM: what the open-source kernel layer is implementing (and what it is still missing)

AIOS is built around one core kernel responsibility: deciding which agent gets the LLM next. That's not a middleware afterthought in its design; it's the job of the kernel layer itself.

Reading the AIOS main branch (documented in GitHub issue #554, opened September 13, 2026) shows exactly how far implementation lags behind ambition. The aios/scheduler/ directory holds four files: __init__.py, base.py, fifo_scheduler.py, and rr_scheduler.py. Two policies. No priority. No fairness logic at all. Which policy actually runs gets picked by an unrelated use_context_manager flag buried in runtime/launch.py, not by any named scheduling policy. The priority field and the set_priority()/get_priority() methods exist on every syscall in aios/syscall/__init__.py, and yet there isn't a single call site for either of them anywhere in the codebase. Per-agent waiting time and turnaround time never get recorded either, because the executor returns before either gets logged. There's currently no way to even measure how the scheduler is performing. There are no scheduler tests in the project.

AgentRM (arXiv:2603.13110, 2026) proposes an alternative: a Multi-Level Feedback Queue paired with admission control, an OS-inspired resource manager for LLM agent systems. It's the approach AIOS issue #554 explicitly weighs against before settling on explicit priority levels plus weighted fair-share with aging. MLFQ naturally pushes CPU-hungry agents down into lower queues without anyone hand-tuning thresholds. But it introduces a whole new abstraction, queue levels, instead of reusing the priority field that already sits unused in the codebase, and proving a hard starvation bound under MLFQ is a tougher formal problem than doing the same under aging.

Issue #554 proposes adding priority levels that actually influence dispatch order, fair-share weights with a real capacity floor per agent, an aging mechanism with a stated and tested starvation bound, and a policy registry selectable by name from config.yaml, and per-agent usage accounting paired with a fairness score.

The gap between what's proposed and what's shipped has been open since roadmap issue #127 in May 2024. Unassigned, unimplemented, for over two years, even as the agent frameworks built on top of AIOS have kept growing in production use.

SPOQ's wave-based dispatch: scheduling derived from task dependency graphs

SPOQ (Specialist Orchestrated Queuing) is solving a different problem than SAGA or Justitia. SPOQ is about task ordering inside a multi-agent software engineering pipeline, not GPU resource allocation. It's about task ordering inside a multi-agent software engineering pipeline.

The mechanism: model task dependencies as a directed acyclic graph, run a topological sort to compute parallel execution waves, and let every task inside one wave run in parallel while waves themselves run in sequence to respect dependency order. That gets maximum parallelism without any coordination overhead between agents figuring out who goes first.

On unbounded synthetic DAGs, this wave-based dispatch achieves a ratio close to the theoretical critical-path lower bound, close enough to optimal that there's little room left to improve, with speedups reaching well over an order of magnitude over running everything sequentially. On a real 2-slot local backend actually making LLM calls, it holds a steady speedup that matches the hardware's concurrency ceiling exactly, proof the gains aren't an artifact of clean synthetic benchmarks.

Two validation gates sit inside the pipeline: one before execution, checking the plan itself, and one after, checking the resulting code, each held to a 95% quality threshold. Catching a bad plan before any compute gets spent on it is far cheaper than catching a bad result after the fact.

Structured SPOQ planning moves coverage from 93.0 up to 99.75, wipes out cyclic plans entirely, and lifts parallelism potential from 31.0 to 75.25. The dual-gate setup on its own cuts defects from 0.34 to 0.20 per task and raises the test pass rate from 91.25% to 99.75%. Add human review into the loop as a schedulable participant, not a passive check, and residual defects drop further still, from 0.47 to 0.03 per task, with pass rate climbing to 99.75%.

None of this is a lab result dressed up for a paper. A longitudinal study spanning 17 repositories, 8,589 commits, and 1,822 completed tasks ran 13,866 tests across 591 test suites, holding a 99.87% pass rate the whole way through.

The lesson that carries past SPOQ itself: once task dependencies are actually known and mapped out, the dependency graph is a far better scheduling signal than arrival time ever was.