MARS: Efficient, Adaptive Co-Scheduling for Heterogeneous Agentic Systems

MARS is an efficient, adaptive co-scheduling system that globally coordinates heterogeneous GPU-CPU resources for autonomous LLM agents by decoupling admission from execution and optimizing state retention, thereby significantly reducing end-to-end latency while maintaining high throughput.

The Gist

Imagine you run a busy, high-tech kitchen. In the past, this kitchen only cooked simple, one-off dishes (like a single text response). The chefs (GPUs) were the only ones who mattered, and the goal was simply to cook as many dishes per hour as possible.

But today, the kitchen has changed. It now runs autonomous agents—think of them as super-chefs who don't just cook a dish, but go on a complex journey to solve a problem. They might cook a bit, then run to the pantry to grab an ingredient (using a tool), check a recipe book (reading a file), come back to the stove, cook a little more, and repeat this loop dozens of times until the job is done.

The paper introduces MARS, a new "Kitchen Manager" designed specifically for this chaotic, multi-step style of cooking. Here is how it works, using simple analogies:

The Problem: The Old Kitchen Was Breaking

The old kitchen managers (existing AI systems) were designed for the "one-off dish" era. When faced with these new, complex agent journeys, they made three big mistakes:

1. The "Stop-and-Go" Trap: When a chef stops cooking to run to the pantry (CPU tool execution), the old manager would either throw away the chef's notes (KV cache) to save space or keep them forever, clogging the counter. If the notes were thrown away, the chef had to rewrite the whole recipe from scratch when they returned, wasting huge amounts of time.
2. The "Big Order" Blockage: If a huge, complex order (a long context) arrived, it would take over the stove and block all the small, quick orders behind it, even if those small orders were ready to go.
3. The "Blind Spot": The manager only watched the stove (GPU). They didn't see that the pantry (CPU) was jammed. So, they kept sending chefs to the stove even though the pantry was full, causing a traffic jam where chefs stood idle waiting for ingredients.

The Solution: MARS (The Smart Kitchen Manager)

MARS fixes this by acting as a central nervous system that sees everything—both the stove and the pantry—and coordinates them perfectly.

1. The "Unified Information Stream" (The Walkie-Talkie)

Instead of guessing, MARS has a live feed connecting the stove and the pantry.

• How it works: Every time a chef pauses to go to the pantry, or returns with an ingredient, a signal is sent instantly. The manager knows exactly why the chef stopped and when they will be back.
• The Benefit: The manager never has to guess. They know exactly how much counter space (memory) to keep for the chef's notes and when to clear space for new orders.

2. The "External Control Plane" (The Bouncer)

Before a new order even enters the kitchen, MARS checks if the kitchen can actually handle it.

• How it works: It looks at two things: Is the stove free? Is the pantry free? If the pantry is jammed with tool tasks, MARS says, "No new orders right now," even if the stove is empty. This prevents the kitchen from getting overwhelmed.
• The Benefit: It stops the kitchen from accepting too many orders at once, which would cause a total collapse where nothing gets finished.

3. The "Internal Agent-Centric Scheduler" (The Smart Dispatcher)

Once orders are inside, MARS decides who cooks next. It doesn't just follow a "First Come, First Served" line.

• How it works:
  • Priority: If a chef is in the middle of a quick, interactive step, MARS lets them go first. If a chef is stuck on a massive, slow recipe, MARS might pause them briefly to let others finish, preventing the "big order" blockage.
  • The "Warm Resume" Trick: MARS decides intelligently whether to keep a chef's notes (KV cache) on the counter. If the chef is coming back in 2 seconds, MARS keeps the notes (saving time). If they are gone for 20 minutes, MARS clears the notes to make room for others. It only keeps the notes when it actually saves time.

The Results: Faster and Smoother

The paper tested MARS in real-world scenarios (like a coding assistant that writes and tests software).

• Speed: MARS made the agents finish their tasks up to 5.94 times faster than the old systems in controlled tests. In a real-world coding setup, it sped up task completion by 1.87 times.
• Reliability: While old systems would get so clogged that they stopped finishing tasks entirely (high "throughput" but zero "goodput"), MARS kept the kitchen running smoothly, ensuring that tasks actually got completed on time.

Summary

Think of MARS as the difference between a kitchen manager who just counts how many pots are on the stove versus one who understands the entire flow of the restaurant. By watching the stove and the pantry simultaneously, and making smart decisions about who cooks next and what notes to keep, MARS ensures that complex, multi-step AI agents can work efficiently without getting stuck in traffic jams.

Technical Summary

1. Problem Statement

The paper identifies a fundamental shift in Large Language Model (LLM) serving paradigms caused by the rise of autonomous agents. Unlike traditional chatbots that perform single-turn inference, agents execute iterative workflows involving multi-turn loops of generation, tool invocation, and state updates. This shift introduces two critical challenges that existing LLM serving engines (e.g., vLLM, TGI) fail to address:

• Temporal Shift (Single-turn $\to$ Multi-turn): Sessions are no longer continuous GPU operations. They pause for tool execution (CPU-bound) and resume later. Existing systems struggle to decide whether to keep the KV cache resident (for fast "warm" resumption) or evict it (to save memory), leading to either memory starvation or expensive prefix recomputation.
• Spatial Shift (GPU-only $\to$ GPU-CPU Co-located): Agentic workloads require coupled execution on both GPUs (inference) and host CPUs (tool execution). Existing systems optimize for GPU token throughput in isolation, ignoring CPU bottlenecks. This leads to Head-of-Line (HoL) blocking, where long prefill requests block short interactive continuations, and coupled queuing, where GPU capacity sits idle while waiting for CPU tool execution.

The core problem is the lack of a system capable of holistic visibility and adaptive co-scheduling across heterogeneous GPU and CPU resources to optimize end-to-end workflow completion rather than just raw token throughput.

2. Methodology: MARS Architecture

MARS (Multi-turn Adaptive Resource Scheduler) is a co-scheduling system designed to bridge the gap between GPU inference and CPU tool execution. It is built on three core pillars:

A. Unified Information Stream

To eliminate the "blind spot" between GPU and CPU states, MARS introduces a low-overhead telemetry path that exports structured boundary events.

• GPU Plane: Reports KV block availability, prefill launch delays, and projected KV demand.
• CPU Plane: Tracks active tool invocations and execution durations to quantify host-side congestion.
• Function: This stream provides real-time, dual-pressure telemetry, allowing the system to make informed decisions based on actual resource contention rather than static heuristics.

B. External Control Plane (Admission Control)

This component decouples admission from execution to prevent resource oversubscription.

• Global Load Balancer: Reorders the waiting queue based on current resource pressure. For example, under high CPU load, it prioritizes GPU-heavy sessions to avoid injecting more tool calls; under KV pressure, it prioritizes smaller sessions.
• Adaptive Admission Controller: Uses an AIMD (Additive Increase Multiplicative Decrease) control loop driven by the Unified Information Stream. It dynamically adjusts the admission window ($W_{adm}$) based on real-time CPU and KV pressure, ensuring requests only enter the data plane when global resources are sufficient.

C. Internal Agent-Centric Scheduler (Data Plane)

Once admitted, the scheduler manages execution ordering and KV residency to minimize the end-to-end critical path.

• Priority-Aware Coordinator: Replaces First-Come-First-Served (FCFS) with a Multi-Level Feedback Queue. It prioritizes requests based on:
  1. Initial KV footprint (smaller = higher priority).
  2. Accumulated service (to prevent starvation).
  3. Waiting time.
     This prevents long prefill tasks from blocking short, latency-sensitive continuations.
• Opportunistic Co-Scheduler: Handles resource constraints dynamically.
  • Chunk Shrinking: If a full prefill cannot fit in memory, it shrinks the token chunk size to allow partial progress rather than blocking.
  • Smart KV Retention: Decides whether to keep a KV cache resident during tool execution. It only retains state if the "warm resumption" benefit outweighs the memory opportunity cost, preventing memory stranding.

3. Key Contributions

1. Workload Characterization: The paper formally identifies the temporal and spatial shifts in agentic workloads and demonstrates how they create dynamically misaligned demands across GPU compute, KV cache capacity, and host CPU resources.
2. Unified Telemetry: Introduction of the Unified Information Stream, which makes heterogeneous resource pressure explicit by exporting execution-boundary events from both GPU and CPU planes.
3. Coupled Control Architecture: A novel design combining an External Control Plane (for admission) and an Internal Agent-Centric Scheduler (for execution) that jointly optimizes admission, scheduling, and KV residency.
4. Implementation & Integration: MARS is implemented on top of vLLM and integrated with the OpenHands coding agent framework, demonstrating practical applicability.

4. Experimental Results

The authors evaluated MARS on H100 and H200 GPUs using models like Qwen3-Coder-30B and GPT-OSS-120B, across benchmarks including SWE-bench, GitTaskBench, and RepoBench.

• Latency Reduction: MARS reduces mean end-to-end latency by up to 5.94× compared to state-of-the-art baselines (including FCFS, Autellix, Infercept, and Continuum) under heavy load.
• Throughput & Goodput: While maintaining nearly maximal system throughput, MARS significantly improves Dynamic SLO-Aware Goodput (the rate of requests completing within latency targets). Baselines often collapse in goodput under load, whereas MARS sustains high completion rates.
• Real-World Deployment: In a realistic deployment with OpenHands, MARS accelerated end-to-end task completion time by up to 1.87×.
• Ablation Studies: Removing the Priority-Aware Coordinator caused a 2×–5× latency increase due to HoL blocking. Removing the External Control Plane caused a 1.5×–3× slowdown due to unmanaged queue buildup.

5. Significance

MARS represents a paradigm shift in LLM serving infrastructure. It moves away from the request-centric, throughput-optimized models of the past toward session-aware, end-to-end workflow optimization.

• Systemic Impact: It solves the "coupled pressure" problem where GPU and CPU resources are interdependent, a critical bottleneck for the next generation of autonomous agents.
• Practicality: By integrating with OpenHands and vLLM, it proves that these architectural changes can be deployed in real-world agentic frameworks without rewriting the entire stack.
• Future Direction: The paper highlights the need for OS-like abstractions in LLM serving to manage stateful, multi-turn contexts, paving the way for more robust and efficient agentic systems.

In summary, MARS provides the necessary control plane and scheduling logic to make heterogeneous agentic systems efficient, scalable, and responsive, addressing the critical gap between raw hardware capability and actual workflow completion.