PaperlayerView exact revision on arXiv

Source-linked AI summary

Workflow-Aware Communication and Computation Scheduling for Mobile Edge AI Agents

Xingqiu He, Chaoqun You, Feng Wang, Zihan Chen, Shuai Wang, Jihong Park

arXiv:2610.29337v1cs.NI

TL;DR

Dynamically revealed agent workflows leave online schedulers with incomplete information about future operations and dependencies, while communication and computation resources jointly shape job latency. The paper models these workflows as dynamic graphs and develops a joint scheduler using a look-ahead cost-to-go surrogate; simulations report lower latency than benchmark schemes across scenarios, with larger reductions under heavy traffic and strong radio contention.

  • Problem

    Agent workflows reveal operations and dependencies from intermediate results, so an online scheduler must allocate resources before future operations are known while accounting for coupled communication and computation.

    Source: §I · p. 1

  • Method

    The paper models partially revealed workflows as dynamic graphs, reformulates weighted completion time as per-slot holding cost, and uses a look-ahead surrogate with completion correction for joint scheduling.

    Source: §I · pp. 1–2

  • Results

    The proposed scheduler outperforms benchmark schemes across diverse scenarios, with the most significant weighted-mean latency reduction under heavy traffic and strong radio contention.

    Source: §I · p. 2, §VI · p. 9

  • Takeaways & Limitations

    The simulations support workflow-aware joint scheduling as an approach that reduces weighted mean completion latency, particularly under heavy traffic and strong radio contention.

    Source: §VI · p. 9

Abstract

from arXiv · show

AI agents are increasingly deployed in mobile edge environments to autonomously handle diverse tasks through multi-step workflows. Unlike conventional dependency-aware tasks with predefined dependency structures, agent workflows are dynamically generated based on intermediate execution results. To minimize the weighted sum of job completion latencies, this paper models partially revealed agent workflows using dynamic workflow graphs and formulates an online scheduling problem that jointly optimizes computation placement, wireless resource block allocation, and edge computing resource allocation. To address the uncertainty of future workflow evolution, we first transform the weighted completion time objective into an equivalent per-slot holding cost and characterize the optimal policy through a Bellman equation. We then construct a tractable look-ahead cost-to-go surrogate based on the revealed workflow and the estimated remaining latencies of active jobs. The proposed scheduling algorithm leverages the surrogate to determine computation placement and uses the resulting operation criticality to allocate wireless and edge computing resources online. Simulation results show that the proposed algorithm outperforms the benchmark schemes across diverse scenarios.

I. INTRODUCTION

Agent workflows are revealed dynamically, so an online scheduler must make resource decisions with incomplete dependency information while balancing communication and computation. The paper models these workflows as dynamic graphs and develops a joint scheduler to minimize weighted job completion latency.

I. INTRODUCTION

  • Dynamic agent workflows differ from conventional dependency-aware tasks because operations and dependencies emerge from intermediate results, leaving future workflow structure unknown to the online scheduler.Source: §I · p. 1
  • The scheduler combines a holding-cost reformulation with a look-ahead surrogate and completion correction to account for downstream dependencies and operation-driven state transitions.It uses the resulting operation criticality to jointly determine computation placement and communication and computation resource allocation.Source: §I · pp. 1–2
  • The proposed algorithm outperforms three benchmarks across scenarios in an event-driven simulator with varied workflows and time-varying communication and computing resources.Source: §I · p. 2

II. RELATED WORK

  • Prior dependency-aware and edge-AI schedulers generally assume known task dependencies or fixed operation graphs, unlike agent workflows that reveal operations during execution.Source: §II · p. 2

A. Dynamic Agent Workflow Model

  • The system model considers jobs arriving over time in a single-cell wireless edge system with devices, a base station co-located with an edge server, and a remote cloud.Source: A. Dynamic Agent Workflow Model · p. 2

1) Dynamic workflow graph:

  • A dynamic workflow graph represents revealed operations and precedence constraints; causal revelation ensures an operation’s incoming edges arrive with it, fixing its predecessor set thereafter.Source: 1) Dynamic workflow graph · pp. 2–3

2) Computation operations:

Computation operations represent agent execution steps and are assigned estimated workloads and feasible execution locations. Communication operations represent wireless data transfers, whose workloads may initially be unknown.

2) Computation operations:

  • A computation operation represents an agent execution step, and its workload is estimated from its type and descriptor using historical data.The descriptor may include a model identifier, input token length, image resolution, or tool category.Source: 2) Computation operations · p. 3

3) Communication operations:

  • Communication operations model wireless transfers of workflow data, and an initially unknown transmission workload is estimated until its actual value becomes available.The operation’s workload is the amount of data to transmit, measured in bits.Source: 3) Communication operations · p. 3

B. Wireless Edge Resource Model

The resource model allocates wireless resource blocks to communication operations and computing capacity to edge-executed operations. Cloud execution uses profiled transmission and computing characteristics, while some operations are fixed to a device.

1) Communication model:

  • Channel quality and the selected modulation and coding scheme determine each communication operation’s per-RB transmission capacity.The model tracks remaining communication workload and represents operation start and finish slots.Source: 1) Communication model · p. 3

2) Computation model:

  • Each edge-executed operation receives computing capacity measured as workload processed per slot, subject to the edge server’s total slot capacity.The model tracks remaining workload and specifies start and finish slots for edge-executed operations.Source: 2) Computation model · pp. 3–4
  • Cloud execution transmission delay is modeled using input and output data sizes, profiled uplink and downlink data per slot, and fixed one-way propagation and processing delay.Cloud computing capacity is also profiled; cloud transmission and computing capacities are beyond the scheduler’s control and estimated from historical data.Source: 2) Computation model · p. 4
  • Some operations, such as tool invocations, must execute on the device providing the corresponding service, with profiled execution time.Their feasible location set contains only that device.Source: 2) Computation model · p. 4

C. Online Workflow-Aware Scheduling Problem

The online problem chooses causal scheduling decisions using only the information available at each slot. It jointly addresses changing workflows and communication and computation resources under uncertainty.

C. Online Workflow-Aware Scheduling Problem

  • At each slot, the scheduler observes revealed workflow graphs, operation states and remaining workloads, job weights, available wireless blocks, and edge capacity.The information state also includes per-resource-block transmission capacity and any placement decision already made.Source: C. Online Workflow-Aware Scheduling… · p. 4
  • Scheduling decisions depend only on the available history and must satisfy precedence, wireless allocation, and edge-computing capacity constraints.The policy set requires feasible causal policies that complete every job almost surely with finite expected weighted latency.Source: C. Online Workflow-Aware Scheduling… · p. 4
  • The scheduler minimizes expected weighted job latency despite unknown future workflow evolution, channel conditions, and resource availability.The problem’s expectation is over workflow evolution, wireless channel variations, and resource-availability fluctuations.Source: C. Online Workflow-Aware Scheduling… · p. 4

IV. ALGORITHM DESIGN

The algorithm design reformulates weighted completion time as per-slot holding cost and characterizes an optimal policy with a Bellman equation. Because that equation is impractical to solve exactly, the paper uses a tractable cost-to-go surrogate.

A. Objective Reformulation

  • The weighted completion-time objective is equivalent to cumulative holding costs for active jobs, with each slot’s cost equal to the sum of their weights.This reformulation makes the objective expressible through costs incurred while jobs remain active.Source: A. Objective Reformulation · p. 5
  • The optimal cost-to-go obeys a Bellman equation that adds the current holding cost to the minimum expected next-state cost over feasible decisions.The feasible decision set is defined by the slot’s scheduling constraints.Source: A. Objective Reformulation · p. 5

IV. ALGORITHM DESIGN

  • Solving the Bellman equation directly is computationally impractical because future workflow operations and resource states are unknown.The paper therefore constructs a tractable surrogate from the revealed workflow and estimated remaining latencies of active jobs.Source: §IV · p. 4, A. Objective Reformulation · p. 5

B. Cost-to-Go Surrogate

The cost-to-go surrogate estimates operation durations and remaining workflow-branch latencies from the revealed dynamic workflow graph. It aggregates these estimates while accounting for uncertain future work at current leaf operations.

1) Converting Workload to Estimated Duration:

  • Communication and computation workloads use different units, so the surrogate converts them into estimated durations to compare operations along workflow paths.The estimates use reference service rates informed by historical data and the current system state.Source: 1) Converting Workload to Estimated… · p. 5
  • Estimated operation durations are not exact completion-time predictions because future resource sharing and channel conditions remain unknown.Their purpose is to express operations in a common time unit so workflow branches can be compared.Source: 1) Converting Workload to Estimated… · p. 5

2) Remaining Latency of Branches:

  • Branch latency includes an operation’s estimated duration and downstream latency, while tail latency is predicted only for current leaves.A leaf’s tail estimate is zero if the agent declares the branch terminated or tail prediction is disabled.Source: 2) Remaining Latency of Branches · p. 5
  • The ordinary maximum successor latency can ignore near-critical branches, so the surrogate uses a smooth maximum to distribute sensitivity among successors.A larger κ makes the approximation closer to the ordinary maximum; a smaller κ distributes sensitivity more evenly.Source: 2) Remaining Latency of Branches · p. 5

3) Look-Ahead Cost-to-Go Surrogate:

The surrogate estimates active jobs’ remaining holding costs from branch-level latency estimates, then discounts farther-future holding costs to distinguish progress on nearly finished jobs. Marginal cost reductions use operation criticality to reflect job weights, branch importance, and reference processing duration.

3) Look-Ahead Cost-to-Go Surrogate:

  • The surrogate’s remaining-latency estimate aggregates branch-level estimates over a job’s ready operations and accounts only for currently active jobs, omitting future arrivals.Only active jobs have observable workflow states and remaining workloads at the current slot.Source: 3) Look-Ahead Cost-to-Go Surrogate · pp. 5–6, 1) Marginal Cost Reduction · p. 6
  • The linear surrogate treats processing orders equivalently when total estimated remaining latency is unchanged, so it cannot distinguish finishing a nearly complete job from equal progress on a long job.The example compares two equal-weight jobs with estimated remaining latencies of one and twenty slots.Source: 3) Look-Ahead Cost-to-Go Surrogate · p. 6
  • Decreasing weights on farther-future holding costs address this limitation; the discrete surrogate is replaced by a continuous relaxation to preserve differentiability.The discount is hζ(τ) = ζ/(ζ+τ), with tunable ζ > 0.Source: 3) Look-Ahead Cost-to-Go Surrogate · p. 6

1) Marginal Cost Reduction:

  • Marginal cost reduction βv(t) estimates the surrogate-cost decrease per unit of workload, with larger values for higher-weight jobs, shorter remaining latencies, and branches more likely to determine job latency.It assumes the operation remains unfinished and therefore omits the discrete workflow change at completion.Source: 1) Marginal Cost Reduction · p. 6

2) Cost Reduction from Operation Completion:

Operation completion is valued by comparing the surrogate before and after the resulting workflow-state changes. Computation placement is chosen by its effect on the surrogate cost across active jobs, including shared edge workload.

2) Cost Reduction from Operation Completion:

  • Operation completion can ready revealed successors, retain a predicted continuation for an unfinished workflow, and change reference service rates, so its cost reduction is evaluated in a hypothetical post-completion state.The hypothetical state marks the operation finished, updates ready operations, and recomputes service rates.Source: 2) Cost Reduction from Operation… · p. 6
  • Operation criticality takes the larger of continuous marginal cost reduction and average cost reduction at completion, capturing both unfinished-work progress and completion effects.The average completion reduction is distributed over the operation’s remaining workload for comparison with the per-unit marginal reduction.Source: 2) Cost Reduction from Operation… · pp. 6–7

D. Computation Placement

  • Placing computation at the edge can increase shared server workload and delay other edge operations, so placement minimizes the cost-to-go surrogate for all active jobs rather than only the current operation’s duration.For each newly ready computation operation, feasible locations are evaluated using updated reference service rates and propagated branch and job latencies.Source: D. Computation Placement · p. 7
  • When exhaustive joint placement is prohibitively expensive, operations are placed sequentially in descending job-weight order, updating candidate edge workload and service rates after each choice.When only a few operations become ready simultaneously, all feasible joint placement combinations are evaluated.Source: D. Computation Placement · p. 7

E. Resource Allocation

After computation placement, wireless RBs and edge capacity are allocated using estimated cost reduction per unit of completed workload. The allocation rules exploit diminishing marginal reductions for radio resources and prioritize edge operations by criticality.

E. Resource Allocation

  • The scheduler first selects computation locations, then computes estimated durations, branch and job latencies, and operation criticalities before allocating RBs and edge capacity and executing actions.The resource-eligible operations depend on the selected locations and resulting active edge workload.Source: E. Resource Allocation · pp. 7–8
  • Wireless RBs are assigned one at a time to the operation with the largest positive marginal surrogate-cost reduction, which is nonincreasing as that operation receives more RBs.Communication and computation resource allocation subproblems are separable and piecewise linear.Source: E. Resource Allocation · p. 7
  • Edge computing capacity is allocated by sorting ready edge-executed operations in descending order of estimated cost reduction per unit of completed workload.The allocation objective is linear in each operation’s allocated edge capacity.Source: E. Resource Allocation · p. 7
  • Computing branch latencies and marginal reductions takes O(M(t)); directly evaluating completion reductions takes O(K(t)M(t)), with caching available to update only affected calculations.The implementation also gives complexity bounds for RB allocation, edge-operation sorting, and placement.Source: E. Resource Allocation · p. 8

A. Simulation Setup

The evaluation uses hidden DAG workflows revealed online and compares the proposed scheduler with three benchmarks. It reports lower weighted mean latency across traffic, resource, and scale settings, alongside runtime and tail-quantile qualifications.

A. Simulation Setup

  • Jobs are hidden DAGs revealed over time; defaults use 12–40 operations, depth 4–12, maximum fan-out four, and endpoints from 20 devices.Jobs arrive according to a Poisson process, with weights sampled from {1, 2, 4}.Source: A. Simulation Setup · p. 8
  • The 10-ms-slot setup varies 5–20 RBs and 3–6 GFLOP/slot edge capacity, and compares Proposed with WSRPT, W-ATLAS, and Myopic.Each experiment contains 300 jobs, and each data point averages 10 random seeds.Source: A. Simulation Setup · p. 8

B. Numerical Results

  • At 6 jobs/s, Proposed reduces weighted mean completion latency by 25.58%, 80.79%, and 52.86% versus WSRPT, W-ATLAS, and Myopic, respectively.The conclusion reports the largest reductions under heavy traffic and strong radio contention, with limited runtime overhead.Source: B. Numerical Results · p. 8, Figure 2 · p. 9, §VI · p. 9
  • With five RBs, Proposed’s improvement rises from 4.13% at 0.5× edge capacity to 6.27% at 2×; with twenty RBs, it is 0.25%–1.56%.The reported gain is largest when communication is the dominant bottleneck.Source: B. Numerical Results · pp. 8–9, Figure 3 · p. 9
  • Proposed’s mean scheduling runtime rises from 0.057 ms for 1–2 active operations to 1.594 ms for 33–48 operations.At 33–48 operations, mean runtimes are 0.482 ms for WSRPT, 0.647 ms for W-ATLAS, and 0.211 ms for Myopic.Source: Figure 4 · p. 9, B. Numerical Results · p. 9
  • Proposed maintains the lowest latency as device count or workflow size increases, with WSRPT the closest benchmark.Across device scales, WSRPT’s latency is 109.08%–115.15% of Proposed’s; the reported baseline ratios also decrease as workflow size increases.Source: Figure 5 · p. 9, Figure 6 · p. 9, B. Numerical Results · p. 9
  • Proposed’s weighted mean latency is 4.50 s versus WSRPT’s 4.81 s, but WSRPT has the lower weighted median, 3.54 versus 3.65 s.Proposed lowers weighted p95 from 12.22 to 10.28 s and weighted p99 from 32.61 to 26.23 s relative to WSRPT; Myopic’s weighted p99 is 15.15 s.Source: Figure 7 · p. 9, B. Numerical Results · p. 9

Related papers

Loading 2610.29337v1…