Source-linked AI summary
Latency-Aware Orchestration for Multi-Agent LLM Workflows on Heterogeneous GPUs
Jinghao Wang, Yifeng Zhang, Xiao Zhou, Yao Lu, Yihui Zhang, Xiaoyang Sun, Tianyu Wo, Xu Wang, Chunming Hu, Renyu Yang
TL;DR
Concurrent multi-agent workflows must reconcile evolving dependencies with heterogeneous, time-varying GPU and serving state, while existing scheduling separates workflow decisions from model lifecycle management. The paper presents a prediction-guided runtime whose Predictor, Constructor, and Scheduler jointly build and adapt physical execution plans. Across three workflow scenarios, it reduces burst makespan and overall p95 latency by up to 36.8% and 25.9%, respectively, over Parrot and Kairos, while saving up to 24.63 GPU-s per completed session.
Problem
Concurrent workflows require joint decisions about readiness, device-specific costs, model lifecycle, placement, ordering, and cumulative memory on heterogeneous GPU pools.
Method
Predictor forecasts activation-device costs and readiness, Constructor builds legal fusion and lifecycle alternatives, and Scheduler jointly selects, places, orders, and revises them under live state.
Results
Up to 36.8% lower burst makespan and 25.9% lower overall p95 completion latency are achieved over Parrot and Kairos, with up to 24.63 GPU-s saved per completed session.
Takeaways & Limitations
Joint physical-graph and lifecycle orchestration improves system-level workflow performance across three heterogeneous-GPU workflow scenarios.
Takeaways & Limitations
Workflow scheduling in the evaluated baselines remains decoupled from model lifecycle management, motivating the runtime’s integrated design.
Abstract
from arXiv · showhide
Concurrent multi-agent workflows expose future dependencies and serving-state requirements while running on heterogeneous GPU pools with time-varying load, model residency, and resource availability. The logical workflow defines the required computation, whereas its physical scheduling units, model-lifecycle actions, resource ordering, and placement must be selected according to the observed pool state. We present a prediction-guided runtime that uses workflow forecasts to construct and optimize a physical execution graph. Predictor estimates device-specific activation latency, peak memory, and model-loading cost, then propagates these predictions through workflow dependencies to forecast activation readiness and future model demand. Constructor builds semantics-preserving fusion and model-lifecycle alternatives, while Scheduler jointly optimizes their selection, placement, and execution order based on the live pool state. Across a workload spanning three workflow scenarios on a heterogeneous GPU pool, our system reduces end-to-end makespan and overall p95 completion latency under burst arrivals by up to 36.8% and 25.9%, respectively, over state-of-the-art workflow schedulers. It also saves up to 24.63 GPU-s per completed session.
1 Introduction
Concurrent multi-agent workflows expose future dependencies and heterogeneous device costs before downstream activations are runnable. The runtime addresses this by constructing legal physical alternatives and jointly scheduling them under live pool state.
- Concurrent agent workflows combine model calls, tools, and control flow whose dependencies, model state, and resource demands unfold over time.
- Heterogeneous GPUs make placement consequential because activations differ in latency, memory demand, and feasibility across devices.
- Existing planners do not jointly evaluate admission-boundary transformations with lifecycle, ordering, placement, and cumulative-memory planning.
- The runtime must construct bounded legal physical alternatives while preserving logical dependencies, request isolation, and completed results.
- Predictor estimates device-specific execution time, peak memory, and model-loading time, then propagates these values through workflow dependencies to forecast activation readiness.
- At each scheduling event, Constructor exposes fusion and lifecycle alternatives, while Scheduler builds a feasible plan, protects ready work, and revises uncommitted decisions using workflow events and telemetry.
2 Background and Motivation
Request-level scheduling leaves model lifecycle and physical admission boundaries disconnected from workflow structure. Physical-graph execution instead uses near-ready visibility, fusion, lifecycle coordination, and cumulative heterogeneous-state checks to plan future work.
- 2.1 Agent Workflows and Serving State: Multi-agent workflow graphs emerge incrementally as model calls interleave with messages, tool results, and control-flow decisions.
- 2.1 Agent Workflows and Serving State: Near-ready activations expose future model, input, and device information before all predecessors complete, enabling bounded preparation without changing logical dependencies.
- 2.2 Limits of Request-Level Execution: 77.3–85.5% of request waiting under both baselines comes from model-availability delays, while loading exceeds token generation in GPU time.
- 2.2 Limits of Request-Level Execution: 97.1–155.1 s, or 39–42%, is the large tail component from repeated admission at same-model boundaries in p95 sessions.
- 2.3 Opportunity for Physical-Graph Execution: Physical execution choices include scheduling-unit boundaries, lifecycle actions, resource order, placement, and state lifetime, even when logical dependencies and results are fixed.
- 2.3 Opportunity for Physical-Graph Execution: Cumulative memory and heterogeneous resource constraints can make individually cheap transformations infeasible when resident weights, KV, engine buffers, and incoming state coexist.
- 2.3 Opportunity for Physical-Graph Execution: The runtime therefore predicts sparse model-device profiles, constructs bounded alternatives across workflows, and jointly selects graph structure, placement, resource order, and state lifetime.
3 Design
The runtime converts resolved workflow windows into semantics-preserving physical execution alternatives, then jointly schedules graph structure, lifecycle actions, placement, and resource order using device-aware forecasts and live pool state. It incrementally commits only executable work and revises the uncommitted suffix as workflow events and telemetry change.
- Adaptive execution: At each scheduling event, Scheduler dispatches a feasible executable prefix and revises uncommitted physical decisions after arrivals, completions, branch updates, or serving telemetry.Execution boundaries refresh pool state and preserve logical workflow semantics while allowing future physical choices to change.
- Predictor: Predictor estimates activation execution, peak-memory, and model-loading costs across model configurations and heterogeneous devices.Cached profiles and runtime feedback support device-specific cost lookup, while execution, memory, and loading estimates serve placement, admission, and lifecycle decisions.
- Predictor: Workflow forecasts propagate device-level estimates through logical dependencies to predict activation release and downstream readiness.Scheduler combines release times with loading, execution, replica queues, and resource precedence when evaluating candidates.
- Constructor: Constructor builds bounded physical alternatives by fusing compatible same-deployment chains and coalescing reusable or shared lifecycle actions across workflows.Fusion preserves external dependencies, per-activation request configurations, outputs, and logical data flow while reducing scheduling boundaries.
- Scheduler: The runtime jointly selects graph structure, replica binding, GPU placement, lifecycle actions, and resource order subject to dependency, deployment, capacity, and cumulative-memory constraints.A device can pass context-domain checks yet remain infeasible when predicted admission memory exceeds capacity or lifecycle demands do not fit the timeline.
4 Evaluation
The evaluation tests the system on heterogeneous GPU workflows under burst and Poisson arrivals, measuring completion time, GPU efficiency, prediction fidelity, and ablation effects. Across these settings, the system improves workload completion and reduces GPU time, with gains linked to prediction quality, cross-workflow lifecycle coordination, fusion, and prefetching.
- End-to-End Performance: 634.2 s: the system finishes 35.8% earlier than Parrot and 36.8% earlier than Kairos under the burst workload.Its overall p95 completion latency is 587.0 s, 25.4–25.9% below the two baselines.
- End-to-End Performance: The system achieves the lowest makespan at both Poisson rates, reducing completion time by 12.4–13.1% and 1.6–6.6% over Parrot and Kairos, respectively.Some Poisson p95 and model-scoped results favor another policy because the global objective can trade a local workflow tail for earlier workload drain.
- GPU-Time Efficiency: 46.26, 15.33, and 65.25 GPU-s per completed session: the system uses less GPU time for GSM8K, MBPP, and QMSum, respectively.These correspond to reductions of 46.9–47.4%, 53.8–56.7%, and 14.5–16.5%; averaged across sessions, savings reach 24.63 GPU-s per completed session.
- GPU-Time Efficiency: Idle residency drives most GPU-time savings, falling to 18.27, 5.25, and 4.31 GPU-s for GSM8K, MBPP, and QMSum.The corresponding baseline ranges are 60.32–60.68, 24.43–26.39, and 10.74–10.92 GPU-s.
- Prediction Accuracy: 8.05% and 7.25%: Predictor achieves the lowest loading-time and runtime WAPE, while reproducing 97.94% of runtime orderings and 97.82% of window-fit outcomes.All predictors exceed 96% decision accuracy, but Predictor has the highest decision fidelity despite formula-based prediction having the lowest peak-VRAM WAPE.
- Predictor and Component Ablations: Cross-workflow lifecycle coordination provides the largest makespan benefit, while node fusion provides the strongest tail-latency benefit and prefetching helps across arrival processes.Restricting lifecycle decisions to one workflow increases makespan by 7.1–16.4%; disabling node fusion raises p95 by 8.5–44.9% and makespan by 3.0–8.1%.
5 Related Work
Prior work spans prediction, model-serving-state management, and scheduling, while this system combines these elements for heterogeneous multi-agent workflows.
- Prediction: Prediction systems estimate runtime, memory, or cross-device performance using neural predictors, transferred measurements, or hardware-aware features.Examples include DNNPerf, PerfSeer, nn-Meter, Habitat, NeuSight, HELP, LitePred, GMorph, and Mercury.
- Serving-state management: Serving-state systems reduce startup or reuse costs through shareable KV caches, optimized checkpoints, tiered storage, and locality-aware scheduling.vLLM, ServerlessLLM, and related systems address model-loading and serving-state management.
- This work: Constructor preserves Agent semantics while fusing deployment-identical chains and adding lifecycle vertices.This extends prior work by representing physical execution alternatives explicitly.
- This work: Scheduler jointly selects bindings, placement, resource order, and cumulative memory.The joint decision scope connects graph construction with lifecycle and resource planning.
6 Conclusion
The paper presents a prediction-guided runtime that separates logical workflow semantics from physical execution and adapts physical decisions to live feedback. Across three workflow scenarios, it improves burst performance and reduces GPU time per completed session relative to Parrot and Kairos.
- Conclusion: The runtime predicts activation–device costs and readiness, constructs legal fusion and model-lifecycle alternatives, and revises uncommitted decisions from feedback.Its Scheduler selects and orders alternatives under live pool state.
- Conclusion: 36.8% lower burst makespan and 25.9% lower overall p95 completion latency are achieved over Parrot and Kairos.The evaluation spans three workflow scenarios.
- Conclusion: 24.63 GPU-s per completed session are saved.This is reported alongside the makespan and p95 improvements.