acceptodds
Under review as a conference paper at ICLR 2027

SWAGES: System-Wide Attention and Guided Evolution for Dynamic Workflow Scheduling

Abstract

Cost-Aware Dynamic Workflow Scheduling (CADWS) repeatedly selects task-VM assignments for workflow tasks and heterogeneous virtual machines (VMs), while minimizing VM rental cost and SLA penalties. Existing learning-based schedulers face two key limitations. First, their policies often focus on individual tasks or workflows without explicitly considering other active workflows or alternative task-VM assignments, limiting system-wide task prioritization and resource allocation. Second, capturing these system-wide interactions requires larger policy models that are more difficult to train efficiently. Gradient-based deep reinforcement learning (DRL) can be unstable, whereas evolution strategies (ES) are more robust but become inefficient in high-dimensional policy spaces because of costly population rollouts and underused transition data. We propose **SWAGES** to address both limitations. Its **System-Wide Graph Attention Network (SWAN)** jointly models active workflows, ready tasks, VMs, and task-VM compatibility, enabling all possible task-VM assignments to be scored under a shared global context. Its **Gradient-Guided Evolution Strategies (GUIDES)** reuse rollout transitions to train twin critics and derive surrogate policy-gradient directions that span a low-dimensional subspace for fitness-based ES search. Extensive experiments show that SWAGES consistently outperforms representative heuristics and recent learning-based CADWS methods, including gradient-based DRL and ES-trained schedulers. Ablation studies further validate the effectiveness of both SWAN and GUIDES.

Primary area:
optimization
Keywords:
cloud workflow scheduling, cloud computing, learning to optimize

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_4akiOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SWAGES for cost-aware dynamic workflow scheduling. It combines a system-wide graph attention network (SWAN), which jointly considers active workflows, ready tasks, and available VMs, with a gradient-guided evolution strategy (GUIDES) that uses critic-derived directions for policy search. The authors evaluate the method on workflow scheduling benchmarks and several continuous-control tasks. The reported results show improvements over existing scheduling and evolutionary learning methods.

Critical strengths

The overall idea is reasonable. Considering all active workflows and task–VM assignments under a shared global context is useful for dynamic scheduling. The use of critic information to guide evolutionary search is also interesting, as it makes use of rollout data without directly relying on policy-gradient updates. The experimental results are encouraging, particularly the improvements over existing learning-based scheduling methods and the tests on continuous-control tasks.

Critical weaknesses
  1. My main concern is whether the experiments sufficiently support the claimed contributions. Although SWAGES achieves good results, the improvements brought by SWAN and GUIDES are not clearly separated. For example, a comparison between SWAN trained with standard ES and SWAN trained with GUIDES would help establish the contribution of the proposed search strategy. I also noticed that Table 1 and Table 2 report substantially different total costs under seemingly identical settings (70.44 vs. 14.51 for S/1). This difference needs clarification. More generally, while the experiments cover several workflow settings and four continuous-control tasks, I am not fully convinced that they establish the broader applicability and computational efficiency of the method.

  2. The novelty and implementation of GUIDES could also be better clarified. Guided evolutionary search using surrogate gradients has been studied before, and the main difference here seems to be how the guidance directions are obtained from replayed transitions and learned critics. However, the relationship between the surrogate objective in Eq. (16) and the centered critic weights in Eq. (63) is not clear to me. This is important for understanding and reproducing the proposed algorithm.

Questions for authors
  1. Could the authors explain the difference in total scheduling costs between Table 1 and Table 2 (also Tables 11–12)? Are different evaluation settings or cost calculations used?

  2. Could the authors provide a more direct comparison to separate the contributions of SWAN and GUIDES, for example, by training SWAN with standard ES? It would also be helpful to clarify the additional computational cost of GUIDES and whether its advantage remains when training time or computational budget is taken into account.

  3. Could the authors clarify how the centered critic weights in Eq. (63) are incorporated into the surrogate objective in Eq. (16)? How is the corresponding guidance gradient computed for the continuous-action tasks?

5 comments

W1 and Q1–Q3. Experimental Validation and Implementation of SWAGES

We thank the reviewer for these constructive comments. We clarify the experimental differences, provide additional controlled comparisons of SWAN and GUIDES, evaluate computational efficiency and generalization, and clarify the guidance-gradient computation.

(1) Q1: Why do Tables 1 and 2 report different costs?

The difference comes from the number of workflows per test instance, not from different cost calculations. Table 1 uses 30 workflows per instance, whereas the original Table 2 uses only 5. The smaller workload was chosen to reduce the computational cost of repeated ablation experiments. We acknowledge that this distinction was insufficiently explained.

To address this concern, we repeated the ablations using 30 workflows per test instance, matching the main evaluation workload. The updated SWAN results are shown in Table R3.

Table R3. SWAN architecture ablation at γdl=1\gamma_{\mathrm{dl}}=1. Total cost reported as mean (std); lower is better.

VariantSML
SWAGES (full)70.43 (1.29)106.82 (4.51)159.83 (10.26)
Full Workflow DAGs76.24 (7.90)109.07 (2.65)166.84 (7.19)
w/o Global Module78.67 (6.54)110.79 (0.82)170.82 (5.95)
w/o Task Transformer83.57 (7.65)120.81 (8.33)174.84 (12.60)
w/o Compatibility85.01 (6.49)121.95 (4.10)177.36 (7.07)
w/o Directional GAT80.61 (6.21)114.58 (0.67)170.54 (0.34)

Removing any SWAN component increases mean total cost across all three scales, confirming the importance of the proposed architecture under the main evaluation workload. The full method also achieves nearly identical mean costs in Table 1 and the updated ablations (70.44 vs. 70.43 for S-scale workflows at γdl=1\gamma_{\mathrm{dl}}=1).

We will clarify the original reduced-workload setting and the evaluation protocol in the revised manuscript.

(2) W1 and Q2: What Are the Independent Contributions of SWAN and GUIDES?

We isolate the two contributions by holding the training algorithm or policy architecture fixed.

SWAN's contribution. Under the same OpenAI-ES optimizer, SWAN achieves mean costs of 73.68, 111.22, and 163.78, compared with 139.05, 231.53, and 370.50 for GATES on S-, M-, and L-scale workflows, respectively. These reductions of 47.0%, 52.0%, and 55.8% demonstrate the benefit of SWAN independently of GUIDES.

GUIDES' contribution. Holding SWAN fixed, we compare GUIDES with standard OpenAI-ES, Random Subspace, REINFORCE Guidance, and mixed-search variants.

Table R4. Comparison of policy search strategies using SWAN at γdl=1\gamma_{\mathrm{dl}}=1. Total cost reported as mean (std); lower is better.

Search strategySML
GUIDES70.43 (1.29)106.82 (4.51)159.83 (10.26)
OpenAI-ES73.68 (1.48)111.22 (5.88)163.78 (12.69)
Random Subspace119.16 (64.51)166.56 (65.65)244.97 (62.06)
REINFORCE Guidance73.08 (4.16)111.28 (4.55)167.71 (11.33)
Mixed search (α=0.2\alpha=0.2)78.28 (8.17)115.18 (7.75)171.28 (10.64)
Mixed search (α=0.5\alpha=0.5)79.51 (7.88)116.40 (10.79)173.24 (18.98)
Mixed search (α=0.8\alpha=0.8)79.55 (7.19)118.60 (10.14)174.58 (15.45)

GUIDES reduces mean cost relative to OpenAI-ES by 4.4%, 4.0%, and 2.4% across the three scales. Random Subspace performs substantially worse, showing that dimensionality reduction alone is insufficient. GUIDES also outperforms REINFORCE Guidance and all tested mixed-search variants, supporting the effectiveness of critic-derived search directions.

Together, these controlled comparisons establish independent performance gains from SWAN's system-wide scheduling architecture and GUIDES' critic-guided evolutionary search.

(3) Q2: What Are the Computational Costs?

Inference latency. Table R7 shows that SWAGES requires only 6.68–8.19 ms per scheduling decision, increasing by just 1.51 ms from S to L scale. Although GATES and SPN-CWS have lower inference latency, SWAGES remains faster than DRL-G across all scales.

Table R7. Average inference time per scheduling decision (ms; lower is better).

ScaleSWAGESGATESSPN-CWSDRL-G
S6.686.251.537.83
M7.266.891.7015.03
L8.195.631.9030.59

This latency is sufficiently low for task-level online scheduling at the evaluated scales, where assignments are made at scheduling decisions rather than continuously during task execution. At the measured L-scale latency, 100 assignments would require only approximately 0.82 seconds of policy inference.

Training efficiency. Although GUIDES incurs additional critic-training computations, its search guidance reduces the wall-clock training time needed to reach a target scheduling cost.

Table R8. Wall-clock training time (hours, mean ± std) to reach target scheduling costs; lower is better.

Method≤ 250≤ 200≤ 180≤ 150
SWAGES2.94 ± 0.803.24 ± 0.893.24 ± 0.894.48 ± 1.25
GATES3.05 ± 0.945.07 ± 1.456.34 ± 1.7210.10 ± 2.41
SPN-CWS6.74 ± 1.799.10 ± 2.2410.84 ± 2.5414.87 ± 3.16
DRL-G3.69 ± 0.5220.18 ± 2.8333.21 ± 4.65—

SWAGES reaches a total cost of 150 in 4.48 hours, compared with 10.10 hours for GATES and 14.87 hours for SPN-CWS. This represents a 55.6% reduction in training time relative to GATES.

These results show that SWAGES achieves low inference latency and faster convergence to target scheduling costs, despite the additional computations required by GUIDES.

(4) W1: Does SWAGES Generalize Beyond the Original Test Settings?

We conducted two additional experiments using the same trained policy without retraining or fine-tuning. They examine generalization to substantially larger workloads and a previously unseen workflow type.

Cross-scale generalization. Table R9 reports performance on 1,000-task workloads, substantially larger than the workflow scales used during training. SWAGES achieves the lowest mean cost across all five deadline settings.

Table R9. Total scheduling cost on 1,000-task workloads (mean ± std; lower is better).

γdl\gamma_{\mathrm{dl}}SWAGESGATESSPN-CWS
1.01,369.7 ± 178.28,806.0 ± 5,144.411,829.3 ± 6,377.6
1.51,340.2 ± 171.311,724.3 ± 8,916.217,549.0 ± 7,401.2
2.01,350.7 ± 189.912,909.1 ± 9,600.617,565.4 ± 8,162.4
2.51,327.6 ± 186.213,229.5 ± 9,287.717,997.2 ± 8,223.0
3.01,341.9 ± 197.913,714.3 ± 9,077.017,454.6 ± 7,474.1

Generalization to unseen workflows. We further evaluated SWAGES on Epigenomics, a workflow type excluded from training.

Table R10. Total scheduling cost on the unseen Epigenomics workflow type (mean ± std; lower is better).

γdl\gamma_{\mathrm{dl}}SWAGESGATESSPN-CWSDRL-G
1.0214.71 ± 6.35633.45 ± 150.23960.50 ± 459.091174.23 ± 741.27
1.5190.82 ± 12.72566.47 ± 65.72677.86 ± 234.391158.68 ± 741.30
2.0169.37 ± 13.96555.54 ± 83.33687.54 ± 115.021143.13 ± 741.35
2.5154.54 ± 12.42593.14 ± 189.45664.35 ± 215.731127.63 ± 741.36
3.0144.18 ± 11.69604.92 ± 138.75644.28 ± 178.041112.23 ± 741.28

SWAGES reduces mean cost relative to GATES by 84.4%–90.2% on the 1,000-task benchmark and 66.1%–76.2% on Epigenomics. These results demonstrate strong generalization to larger workloads and unseen workflow structures without retraining.

(5) Q3: How Are the Guidance Gradients Computed?

We agree that the relationship between Eq. (16) and the centered critic weights in Eq. (63) was unclear. The guidance computation should be defined consistently for discrete and continuous actions.

Discrete actions (CADWS). The twin critics evaluate all possible task–VM assignments, giving Q^(s,a)=min⁡jQϕj(s,a)\widehat Q(s,a)=\min_j Q_{\phi_j}(s,a). For each guidance batch Bk\mathcal B_k, the surrogate objective is

\sum_{s\in\mathcal B_k} \sum_{a\in\mathcal A(s)} \pi_\theta(a\mid s)\widehat Q(s,a).$$ Its gradient is evaluated at the current center parameters $\theta_g$, with the critics held fixed. This objective directly weights every possible assignment by its critic-estimated value. **The batch-centered replay-action weights in Eq. (63) are not part of this formulation** and will be removed to eliminate the inconsistency. **Continuous actions (robotics).** For a differentiable deterministic actor $\mu_\theta(s)$, the corresponding surrogate objective is $$\mathcal J_k^{\mathrm{cont}}(\theta)= \frac{1}{B_G} \sum_{s\in\mathcal B_k} \widehat Q(s,\mu_\theta(s)).$$ The guidance gradient is computed by backpropagating through the critic with respect to the continuous action and then through the actor. The resulting directions are normalized and orthogonalized to construct the search subspace. **In both cases, these surrogate gradients guide ES population sampling; they do not directly update the policy.** The policy update remains determined by rollout fitness. We will remove the inconsistent Eq. (63) and update the appendix and pseudocode to precisely present the guidance-gradient calculations described above.
Reviewer_LNxwOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SWAGES (Cost-Aware Dynamic Workflow Scheduling, CADWS), a scheduling framework for the SWAGES problem. The framework consists of two main components: SWAN (System-Wide Graph Attention Network) and GUIDES (Gradient-Guided Evolution Strategies). SWAN is a scheduling policy network based on a bidirectional graph neural network that assigns tasks to appropriate virtual machines (VMs). GUIDES, in turn, provides the corresponding policy optimization and training strategy. Specifically, GUIDES leverages rollout data to train Twin-CRiTIC, constructs a low-dimensional search subspace, and subsequently updates the policy using newly generated rollout data. The authors evaluate SWAGES across workflows with different characteristics and under varying deadline factors. The reported results demonstrate substantial performance improvements over several baselines, including ProLis, GRP-HEFT, DRL-G, SPN-CWS, and GATES.

Critical strengths

S1. Clear problem formulation and practical relevance.\textbf{S1. Clear problem formulation and practical relevance.} The paper provides a clear description of the problem background and a well-defined mathematical formulation. The problem is also practically relevant, particularly in real-world production environments where workflow scheduling must balance execution costs and deadline constraints.

S2. Well-motivated and clearly structured methodological contributions. \textbf{S2. Well-motivated and clearly structured methodological contributions. } SWAN and GUIDES address key challenges in policy design and policy optimization, respectively. The motivation behind the proposed components is clearly articulated, and the paper presents a coherent narrative that connects the identified challenges to the proposed solutions.

Critical weaknesses

W1. Inconsistencies in the reported experimental results undermine confidence in the empirical findings.\textbf{W1. Inconsistencies in the reported experimental results undermine confidence in the empirical findings.} Some of the values reported in the tables appear inconsistent, raising concerns about the reliability and reproducibility of the experimental results. For example, in Table 1, the reported mean total cost for (S + γdl=1\gamma_{dl} = 1) is 70.44 over 30 test runs, whereas Table 2 reports a value of 14.51 over 10 test runs. Such a substantial discrepancy in the mean total cost is difficult to reconcile if the two results are intended to reflect the same experimental setting. If different test instances or evaluation protocols were used, the validity and comparability of the ablation results would need further clarification. The authors should provide more detailed information about the evaluation protocol, including the test instances, random seeds, and aggregation procedures, to establish the reliability of the reported results. In addition, the standard deviations reported for DRL-G in Table 1 differ only marginally between the M and L scales (114.4× and 444.7×, respectively), which appears unusual compared with the patterns observed for the other methods. The authors should clarify and explain this observation to improve confidence in the experimental results.

W2. Insufficient analysis of computational overhead and generalization capability.\textbf{W2. Insufficient analysis of computational overhead and generalization capability.} The paper provides limited information about the inference and training costs of SWAGES. Since SWAN's decision space scales with the number of tasks and the number of VMs (Ntasks×NVMs)(N_{\text{tasks}} \times N_{\text{VMs}}), the computational overhead could become substantial in realistic scheduling scenarios. The authors should provide a more comprehensive analysis of training costs, inference latency, and end-to-end execution time. In practical production systems, heuristic scheduling methods remain attractive because of their efficiency and robustness. Therefore, it is important to establish whether SWAGES offers practical advantages when its computational overhead is taken into account. Furthermore, the generalization experiments appear to be limited primarily to variations in the deadline factor (γdl\gamma_{dl}). Additional experiments across different workflow structures, scales, resource configurations, or unseen environments would help determine whether the proposed policy generalizes effectively and can be applied to a broader range of scheduling scenarios.

W3. Insufficient ablation studies to isolate the contributions of GUIDES.\textbf{W3. Insufficient ablation studies to isolate the contributions of GUIDES.} The current ablation experiments do not adequately establish the sources of the performance gains achieved by GUIDES. In particular, the paper does not sufficiently explain the individual contributions of key design choices, such as Twin-CRiTIC learning and the critic-derived guidance subspace. More targeted ablation studies are needed to isolate the effects of these components and demonstrate how each contributes to the overall performance improvement.

Questions for authors

Q1. Clarification of inconsistencies in the reported results. \textbf{Q1. Clarification of inconsistencies in the reported results. } As discussed in Weakness 1, could the authors explain the substantial discrepancy between the results reported in Table 1 and Table 2? Specifically, why does the reported mean total cost differ so significantly between the two settings? Are the test instances, random seeds, or evaluation protocols different? The authors should also clarify the unusual standard deviation pattern observed for DRL-G in Table 1.

Q2. Transferability, deployment overhead, and end-to-end efficiency.\textbf{Q2. Transferability, deployment overhead, and end-to-end efficiency.} As discussed in Weakness 2, how well does SWAGES transfer to new workflows or execution environments? Does the policy need to be retrained or fine-tuned whenever a new workflow or environment is encountered? What are the training and inference costs after deployment in a new environment? Could the authors provide end-to-end runtime measurements, including any required adaptation or training overhead, to demonstrate the practical efficiency of the proposed approach?

3. Sources of performance gains from GUIDES.\textbf{3. Sources of performance gains from GUIDES.} As discussed in Weakness 3, which components of GUIDES contribute most significantly to its performance improvements? Could the authors provide more comprehensive ablation studies to quantify the individual contributions of Twin-CRiTIC learning, the critic-derived guidance subspace, and other key design choices? Although the appendix includes experiments on robotic control, additional ablation studies specifically targeting the CADWS problem are still needed to establish the effectiveness of these components in the paper's primary application domain.

7 comments

We appreciate the reviewer’s constructive and insightful comments. To provide a clear and well-organized response, we address each weakness and question individually in detail.

W1 and Q1. Experimental Consistency and Reliability

We clarify the evaluation settings, provide additional ablation results under the main experimental workload, and explain the standard deviation patterns observed for DRL-G.

(1) Why do Tables 1 and 2 report different costs?

The difference arises from the number of workflows per test instance, not from different cost calculations. Table 1 uses 30 workflows per instance, whereas the original Table 2 uses only 5. Both use the same total-cost objective, comprising VM rental costs and SLA penalties.

The smaller workload was originally chosen to reduce the computational cost of independently training multiple ablation variants, following the practice of reduced-scale ablation experiments in computationally intensive ML research [1, 2, 3, 4]. However, we acknowledge that this experimental distinction was insufficiently explained.

To resolve this concern, we repeated the ablation experiments using 30 workflows per test instance, matching Table 1. The updated results are reported below.

Table R3. SWAN architecture ablation at γdl=1\gamma_{\mathrm{dl}}=1. Total cost reported as mean (std).

VariantSML
SWAGES70.43 (1.29)106.82 (4.51)159.83 (10.26)
Full Workflow DAGs76.24 (7.90)109.07 (2.65)166.84 (7.19)
w/o Global Module78.67 (6.54)110.79 (0.82)170.82 (5.95)
w/o Task Transformer83.57 (7.65)120.81 (8.33)174.84 (12.60)
w/o Compatibility85.01 (6.49)121.95 (4.10)177.36 (7.07)
w/o Directional GAT80.61 (6.21)114.58 (0.67)170.54 (0.34)

Table R4. GUIDES search ablation using SWAN at γdl=1\gamma_{\mathrm{dl}}=1. Total cost reported as mean (std).

VariantSML
GUIDES (α=0\alpha=0)70.43 (1.29)106.82 (4.51)159.83 (10.26)
Mixed search (α=0.2\alpha=0.2)78.28 (8.17)115.18 (7.75)171.28 (10.64)
Mixed search (α=0.5\alpha=0.5)79.51 (7.88)116.40 (10.79)173.24 (18.98)
Mixed search (α=0.8\alpha=0.8)79.55 (7.19)118.60 (10.14)174.58 (15.45)
OpenAI-ES (α=1\alpha=1)73.68 (1.48)111.22 (5.88)163.78 (12.69)

The updated results confirm the original findings under the main experimental workload. Removing any SWAN component increases mean scheduling cost across all three scales. GUIDES also consistently outperforms the alternative search strategies, including OpenAI-ES. These results provide further evidence for the independent effectiveness of SWAN and GUIDES.

(2) Clarification of the evaluation protocol

We will clarify the experimental settings and aggregation procedures in the revised paper. Table R5 summarizes the protocols for the main experiments and updated ablations.

Table R5. Evaluation protocols for the main experiments and updated ablations.

SettingMain experimentsUpdated ablations
Workflow typesCyberShake, Montage, Inspiral, SIPHTSame
Training scaleSS
Training γdl\gamma_{\mathrm{dl}}5.05.0
Testing scalesS, M, LS, M, L
Testing γdl\gamma_{\mathrm{dl}}1, 1.5, 2, 2.5, 31
Workflows per test instance3030
Test instances3030
Random seeds3010
Cost calculationVM rental cost + SLA penaltiesSame

Under the same workload configuration and cost calculation, the full SWAGES model achieves nearly identical mean total costs in the main and updated ablation experiments (70.44 vs. 70.43 on S-scale workflows at γdl=1\gamma_{\mathrm{dl}}=1), further supporting the consistency of our experimental results.

References

[1] Malladi et al. Fine-Tuning Language Models with Just Forward Passes. NeurIPS 2023.

[2] Robine et al. Smaller World Models for Reinforcement Learning. Neural Processing Letters, 2023.

[3] Zhang et al. Bam! just like that: Simple and efficient parameter upcycling for mixture of experts. Advances in Neural Information Processing Systems, 2024.

[4] Joshi et al. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 2022.

W2 and Q2. Computational Efficiency and Generalization

We conducted additional experiments to evaluate inference latency, wall-clock training cost, and generalization to larger and unseen workflows without retraining.

(1) Computational Efficiency: Inference and Training Costs

Inference latency. Table R7 shows that SWAGES requires only 6.68–8.19 ms per scheduling decision, increasing by just 1.51 ms from S to L scale. Although GATES and SPN-CWS have lower inference latency, SWAGES is consistently faster than DRL-G, particularly on L-scale workflows (8.19 vs. 30.59 ms). This latency is sufficiently low for practical task-level cloud workflow scheduling, where decisions are made when assigning tasks rather than continuously during their execution. For example, at the measured L-scale latency, 100 task assignments would require only 0.82 seconds of policy inference in total.

Table R7. Average inference time per scheduling decision (ms; lower is better).

ScaleSWAGESGATESSPN-CWSDRL-G
S6.686.251.537.83
M7.266.891.7015.03
L8.195.631.9030.59

Training efficiency. While GUIDES introduces additional critic-training overhead, its improved search efficiency reduces the wall-clock time required to achieve a given scheduling cost. As shown in Table R8, SWAGES reaches a total cost of 150 in 4.48 hours, compared with 10.10 hours for GATES and 14.87 hours for SPN-CWS. This represents a 55.6% reduction in training time relative to GATES.

Table R8. Wall-clock training time (hours, mean ± std) to reach different total-cost thresholds. Lower is better.

Method≤ 250≤ 200≤ 180≤ 150
SWAGES2.94 ± 0.803.24 ± 0.893.24 ± 0.894.48 ± 1.25
GATES3.05 ± 0.945.07 ± 1.456.34 ± 1.7210.10 ± 2.41
SPN-CWS6.74 ± 1.799.10 ± 2.2410.84 ± 2.5414.87 ± 3.16
DRL-G3.69 ± 0.5220.18 ± 2.8333.21 ± 4.65—

These results demonstrate that SWAGES maintains millisecond-level inference latency while achieving substantially better training efficiency in terms of time to reach a target scheduling cost, despite the additional critic computations.

(2) Generalization: Larger and Unseen Workflows

To assess generalization beyond variations in deadline constraints, we conducted two additional experiments using the same trained SWAGES policy without retraining or fine-tuning.

Cross-scale generalization. We evaluated SWAGES on workflows containing 1,000 tasks, substantially larger than the workflow sizes used during training. Table R9 shows that SWAGES achieves the lowest mean cost across all five deadline settings, reducing cost relative to GATES by 84.4%–90.2%. This demonstrates that the learned policy remains effective on substantially larger workflow DAGs.

Table R9. Total scheduling cost on 1,000-task workflows, reported as mean ± std (lower is better).

γdl\gamma_{\mathrm{dl}}SWAGESGATESSPN-CWS
1.01,369.7 ± 178.28,806.0 ± 5,144.411,829.3 ± 6,377.6
1.51,340.2 ± 171.311,724.3 ± 8,916.217,549.0 ± 7,401.2
2.01,350.7 ± 189.912,909.1 ± 9,600.617,565.4 ± 8,162.4
2.51,327.6 ± 186.213,229.5 ± 9,287.717,997.2 ± 8,223.0
3.01,341.9 ± 197.913,714.3 ± 9,077.017,454.6 ± 7,474.1

Generalization to unseen workflow structures. We further evaluated SWAGES on Epigenomics, a workflow type excluded from training. As shown in Table R10, SWAGES achieves the lowest mean cost across all deadline settings, reducing cost relative to GATES by 66.1%–76.2%, without any retraining or fine-tuning.

Table R10. Total scheduling cost on the unseen Epigenomics workflow, reported as mean ± std (lower is better).

γdl\gamma_{\mathrm{dl}}SWAGESGATESSPN-CWSDRL-G
1.0214.71 ± 6.35633.45 ± 150.23960.50 ± 459.091174.23 ± 741.27
1.5190.82 ± 12.72566.47 ± 65.72677.86 ± 234.391158.68 ± 741.30
2.0169.37 ± 13.96555.54 ± 83.33687.54 ± 115.021143.13 ± 741.35
2.5154.54 ± 12.42593.14 ± 189.45664.35 ± 215.731127.63 ± 741.36
3.0144.18 ± 11.69604.92 ± 138.75644.28 ± 178.041112.23 ± 741.28

Together, these experiments demonstrate that SWAGES generalizes to substantially larger workflows and previously unseen workflow structures without retraining, while maintaining low inference latency and competitive wall-clock training efficiency.

W3 and Q3. What Drives the Performance Gains of GUIDES?

To identify the sources of GUIDES' performance gains, we conducted additional controlled experiments comparing GUIDES with three alternative search strategies under the same SWAN architecture and experimental settings: standard OpenAI-ES, Random Subspace, and REINFORCE Guidance.

Table R11. Comparison of policy search strategies at γdl=1\gamma_{\mathrm{dl}}=1. Values report mean total cost (standard deviation).

MethodSML
GUIDES70.43 (1.29)106.82 (4.51)159.83 (10.26)
OpenAI-ES73.68 (1.48)111.22 (5.88)163.78 (12.69)
Random Subspace119.16 (64.51)166.56 (65.65)244.97 (62.06)
REINFORCE Guidance73.08 (4.16)111.28 (4.55)167.71 (11.33)

The results establish three key findings.

(1) Benefit over standard ES. GUIDES reduces mean cost relative to OpenAI-ES by 4.4%, 4.0%, and 2.4% on S-, M-, and L-scale workflows, respectively, demonstrating the benefit of incorporating learned search guidance into fitness-based evolutionary optimization.

(2) Importance of informative search directions. Random Subspace performs substantially worse and exhibits much greater variability. This demonstrates that restricting ES to a low-dimensional subspace alone is insufficient; the quality of the search directions is critical.

(3) Effectiveness of critic-derived guidance. GUIDES also outperforms REINFORCE Guidance across all three scales, reducing mean cost by 3.6%, 4.0%, and 4.7%, respectively. This supports the effectiveness of learning action-value estimates from population transitions to construct evolutionary search directions, rather than relying on an alternative policy-gradient estimator.

Together, these comparisons show that GUIDES' improvements come from using critic-derived directions to guide low-dimensional evolutionary search, rather than dimensionality reduction or conventional ES alone.

Reference

[1] Bharathi, S., Chervenak, A., Deelman, E., Mehta, G., Su, M. H., & Vahi, K. (2008, November). Characterization of scientific workflows. In 2008 third workshop on workflows in support of large-scale science (pp. 1-10). IEEE.

Reviewer_fQckOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a scheduling framework, where a System-Wide Graph Attention Net- work (SWAN) jointly models active workflows, ready tasks, VMs, and task–VM compatibility, enabling all possible task–VM assignments to be scored under a shared global context. Its Gradient-Guided Evolution Strategies (GUIDES) reuse rollout transitions to train twin critics and derive surrogate policy-gradient directions that span a low-dimensional subspace for fitness-based ES search.

Critical strengths
  • The proposed scheduler can do complex decision making, e.g., it jointly determines task priority and VM allocation rather than scheduling each task in isolation.
  • The experiments are sufficient.
Critical weaknesses
  • I am not sure about the novelty of this work. There are so many existing works on deciding vm allocation and task scheduling, especially in the areas of systems and networking. The proposed method is similar to many of them, i.e., a model-free, gradient-free evolutionary policy-search scheduler.
Questions for authors

GUIDES introduces extra hyper-parameters (K, critic LR, replay size, update counts) requiring tuning?

3 comments

We sincerely thank the reviewer for the constructive and insightful feedback. Below, we address Weakness 1 (W1) and Question 1 (Q1) in detail.

W1. Novelty of SWAGES

We agree that VM allocation and task scheduling have been extensively studied. SWAGES introduces two distinct advances: SWAN jointly evaluates task–VM assignments across all active workflows, while GUIDES learns critic-guided search directions from population-rollout transitions to improve evolutionary policy optimization. We clarify how each contribution advances prior methods below.

1. SWAN: System-wide comparison of task–VM assignments

GATES [1] and GOODRL [2] allocate a VM or machine to a given ready task. SWAN instead scores every possible task–VM pair across active workflows, jointly determining task priority and VM allocation. Its representation comprehensively captures remaining workflow structures, competition among ready tasks, VM alternatives, and assignment-specific timing and cost. Importantly, it includes active workflows with no currently ready tasks, whose ongoing execution still affects resource availability and future task readiness.

Although Decima [4] also considers multiple workflows through global DAG representations, its scheduling decisions concern stage selection and parallelism allocation. SWAN introduces a different decision architecture that jointly scores all possible task–VM assignments across active workflows. By integrating cross-workflow attention, contextualized task and VM representations, and assignment-specific timing and cost features, SWAN compares competing assignments under shared resource constraints. Its key novelty lies in combining system-wide workflow awareness with direct, pairwise task–VM evaluation, enabling joint task prioritization and VM allocation within a single policy decision.

Table R1 fixes the training algorithm to OpenAI-ES. SWAN reduces mean cost relative to GATES by 47.0%, 52.0%, and 55.8% on small, medium, and large workflows, respectively. These gains are obtained without GUIDES, demonstrating the independent benefit of SWAN.

Table R1. Mean total cost of policy architectures trained with OpenAI-ES at γdl=1\gamma_{\mathrm{dl}}=1.

Policy architectureSML
SPN-CWS140.30243.58370.30
GATES139.05231.53370.50
SWAN73.68111.22163.78

(2) GUIDES: Learning evolutionary search directions from population experience

Guided ES [3] introduced surrogate-gradient-guided search, but typically constructs its search subspace from a history of available gradients. GUIDES addresses a different challenge: how to derive effective search guidance directly from the transitions generated by ES populations. Rather than using each costly rollout only for its scalar fitness, GUIDES reuses its transitions to train twin critics and estimate multiple surrogate policy-gradient directions from independent replay batches. All directions are computed at the current center policy and orthogonalized into a generation-specific search subspace, instead of relying on gradients from previous policy parameters.

Importantly, GUIDES uses learned gradients to guide evolutionary exploration, not to update the policy directly. Unlike evolutionary–RL hybrids such as ERL [5] and CEM-RL [6], which incorporate gradient-based actor learning, GUIDES retains fitness-based ES updates while using critic-derived directions solely to guide population sampling. Each rollout therefore serves two complementary purposes: evaluating policy fitness and providing reusable experience to improve subsequent search. This is the key algorithmic distinction from conventional ES, Guided ES, and gradient-based evolutionary–RL hybrids.

Holding the SWAN architecture fixed, Table R2 shows that GUIDES reduces mean cost over OpenAI-ES by 4.4%, 4.0%, and 2.4% across the three workflow scales. It also outperforms Random Subspace and REINFORCE Guidance, supporting the effectiveness of the proposed critic-derived search directions.

Table R2. Mean total cost (standard deviation) of search strategies using SWAN at γdl=1\gamma_{\mathrm{dl}}=1 .

Search strategySML
GUIDES70.43 (1.29)106.82 (4.51)159.83 (10.26)
OpenAI-ES73.68 (1.48)111.22 (5.88)163.78 (12.69)
Random Subspace119.16 (64.51)166.56 (65.65)244.97 (62.06)
REINFORCE Guidance73.08 (4.16)111.28 (4.55)167.71 (11.33)

Together, these controlled comparisons demonstrate two distinct contributions: SWAN enables system-wide evaluation of task–VM assignments for joint scheduling, while GUIDES transforms population-rollout experience into critic-guided evolutionary search without sacrificing fitness-based optimization. Their independent performance gains provide strong empirical evidence for the effectiveness of both innovations.

References

[1] Shen et al. GATES: Cost-aware Dynamic Workflow Scheduling via Graph Attention Networks and Evolution Strategy. IJCAI 2025.

[2] Yang et al. Graph Assisted Offline-Online Deep Reinforcement Learning for Dynamic Workflow Scheduling. ICLR 2025.

[3] Maheswaranathan et al. Guided Evolutionary Strategies: Augmenting Random Search with Surrogate Gradients. ICML 2019.

[4] Mao et al. Learning Scheduling Algorithms for Data Processing Clusters. SIGCOMM 2019.

[5] Khadka et al. Evolution-guided policy gradient in reinforcement learning. Advances in Neural Information Processing Systems 2018.

[6] Pourchot et al. CEM-RL: Combining evolutionary and gradient-based methods for policy search. ICLR 2019.

Q1. How Sensitive Is GUIDES to Hyperparameters?

To directly assess the sensitivity of GUIDES to hyperparameter selection, we conducted a dedicated study varying two key parameters: the subspace dimension KK, which determines the number of critic-guided search directions, and the critic learning rate ηc\eta_c, which controls critic training. Each parameter was varied independently, with all other settings fixed.

Table R3. Hyperparameter sensitivity of GUIDES. Total cost reported as mean (std), with lower values indicating better performance.

KKMean (Std)ηc\eta_cMean (Std)
1273.88 (2.03)5×10−55\times10^{-5}73.94 (6.55)
1672.62 (1.82)1×10−41\times10^{-4}73.65 (0.95)
2473.77 (2.11)3×10−43\times10^{-4}72.62 (1.82)
3272.62 (1.51)5×10−45\times10^{-4}73.27 (5.20)

The mean total cost varies by at most 1.8% across all tested configurations, demonstrating that GUIDES is not highly sensitive to these hyperparameters in terms of average performance.

We select K=16K=16 because it achieves nearly identical mean cost to K=32K=32 while requiring only half as many guidance directions. We adopt ηc=3×10−4\eta_c=3\times10^{-4} because it achieves the lowest mean cost among the tested learning rates. These results justify our default settings without requiring extensive hyperparameter tuning. The full analysis is also provided in Appendix G (Table 10).

Dear Reviewer fQck,

Thank you again for your constructive feedback. Following your suggestions, we have conducted additional experiments and analyses, and provided detailed responses to address your concerns.

With only two days remaining in the rebuttal discussion period, we would greatly appreciate it if you could review our additional experimental results and analyses, and let us know whether they have adequately addressed your concerns. We would be happy to provide further clarification if needed.

Thank you for your time and consideration.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.