acceptodds
Under review as a conference paper at ICLR 2027

SCHEMA: Hierarchical Reinforcement Learning for Scheduling Under Communication Contention

Abstract

Scheduling a large graph of dependent tasks on a small pool of machines is a foundational problem in distributed and high-performance computing, with applications in cloud job scheduling, compiler operator placement, and computation-graph execution on accelerators, among others. It is hardest when tasks vastly outnumber machines, where communication, not computation, dominates makespan. Most schedulers treat the cost of moving data between machines as fixed and known in advance. Under contention this fails. When data transfers compete for shared resources, the cost of communication is no longer fixed but depends on the scheduler's own earlier placements. A value function trained under static costs therefore mispredicts the makespan actually achieved, and the error grows as contention increases. SCHEMA is a reinforcement-learning framework built around this effect. It casts scheduling as a hierarchical Markov decision process whose two levels, selecting a task, then its machine, are pointer networks that attend over the current frontier, keeping inference tractable as graphs reach tens of thousands of nodes. Rather than a fixed cost table, communication is modeled as an environment of capacity-limited link tiers whose occupancy grows as tasks are placed; SCHEMA predicts the tier each data transfer would use under current load and exposes this to the policy alongside structural graph features. Trained with PPO and evaluated on four workloads from 90 to 16,208 nodes against eight classical and learned baselines, SCHEMA achieves shorter schedules, and its margin over the strongest baseline improves with graph size, reaching 29% on the largest workload. Ablation studies attribute independent gains to the congestion-aware environment, the tier-estimation features, and the hierarchical policy, and removing any one lengthens the largest schedule by more than 75%.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Scheduling, Communication Contention, Hierarchical Reinforcement Learning, Directed Acyclic Graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_bqxUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes SCHEMA for scheduling DAG tasks on multi-machine platforms where communication resources are contended. The method uses a two-level policy: it first selects a ready task and then selects a machine for it. The environment models the interconnect as capacity-limited link tiers; a transfer uses the cheapest tier with available capacity and is escalated to a more expensive tier when that tier is full. The policy input includes the estimated transfer cost under current tier occupancy. The paper compares SCHEMA with classical and learned baselines on four task graphs and reports a 29.4% makespan reduction over the strongest baseline on the largest graph, MATINV, with 16,208 nodes.

Critical strengths
  1. The paper addresses a practically important problem: communication contention in DAG scheduling on scarce machines. Feeding current link occupancy back into task selection and machine assignment is a clear and reasonable design idea.
  2. The method framework, feature design, and ablation study are relatively clear. The final schedules of all methods are scored by the same evaluator, so the makespan evaluation protocol is relatively consistent.
  3. On the largest and most communication-heavy graph, MATINV, SCHEMA's advantage over baselines is substantial, suggesting that incorporating contention into the environment may help in large-scale, machine-scarce settings.
Critical weaknesses
  1. Novelty and positioning need to be sharper. Communication contention has been explicitly modeled before, and DOPPLER also uses a two-level operation-then-device policy. The clearer contribution of this paper is the combination of a capacity-limited tiered link-occupancy model and its features with joint task/machine learning. However, the experiments do not compare against existing contention-aware schedulers, nor do they discuss recent methods. It is therefore difficult to judge the incremental benefit of this combination.
  2. The DOPPLER baseline adaptation is unclear. DOPPLER originally learns device placement, with an asynchronous runtime determining execution order; SCHEMA constructs task order and machine assignment step by step. Appendix E does not sufficiently explain how DOPPLER's placement is converted into the schedule required by SCHEMA's evaluator, nor does it clearly state what reward is used in DOPPLER's Stage-II simulated training and whether the same tiered-contention environment is used. If DOPPLER is trained under a static communication model but evaluated under contention, the comparison may be unfair. The use of only a single placement sweep for Placeto also needs justification.
  3. The communication simulator lacks grounding and parameter justification. The capacities and per-unit costs in Table 6 have no hardware source, measurement method, or units, and the per-link M2M costs are not fully listed. The model lets a transfer occupy a tier until the successor task starts rather than until data transmission completes; data on the same machine may also be moved to GROUP or GLOBAL when LOCAL is full. Because the main gains depend on this simulator, the authors need to explain which actual resources these rules correspond to (link bandwidth, ports, buffers, or reservation mechanisms) and validate or analyze the sensitivity of conclusions to parameter changes.
  4. Experimental coverage and statistical reporting are insufficient. All four task graphs use a fixed 32-machine configuration; the key ablation is performed only on the non-public MATINV graph; the main results report only the best makespan, without multi-seed means, variance, or confidence intervals; and scheduling generation time and training/inference overhead are missing. The CCR figure shows the difference between HEFT's static estimate and the contention-simulated result for the same schedule, rather than directly showing how SCHEMA's advantage over baselines varies with contention. At minimum, ablation or sensitivity results should be added on the public graphs (ROBOT/SPEC/GEMM).
  5. RL implementation details are insufficient for reproducibility. Although the paper gives the overall MDP, policy, and PPO formulas, it remains unclear how the value network is organized, how the task policy and machine policy share or separate value estimates, how the joint task–machine action participates in PPO updates, how rollouts and batches are organized, whether a separate model is trained for each graph, and how actions are selected at evaluation (sampling or greedy). In addition, the sum of step rewards equals the final makespan only without discounting, whereas Table 4 uses γ=0.99. The claim that maximizing return is equivalent to minimizing final makespan needs to be corrected or justified as an approximation under discounting.
  6. Writing and figures need improvement. Figure 1 is information-dense, some fonts are too small, and the correspondence between modules and equations is not clear enough. It should be redrawn as a proper vector figure with consistent fonts, alignment, and arrows.
Questions for authors
  1. How were the parameters in Table 6 obtained? Please provide units, the complete per-link M2M costs, hardware measurements, or a parameter-sensitivity study.
  2. Why does a link resource remain occupied until the successor task starts? If data transmission has finished but the task is still waiting for a machine, how is this handled? What is the physical meaning of moving same-machine data to GROUP/GLOBAL when LOCAL is full?
  3. How is DOPPLER's device placement converted into the task schedule used by your evaluator? Which environment produces its Stage-II reward, and does that environment also use tiered contention? What is the rationale for using only a single placement sweep for Placeto?
  4. It is suggested to add contention-aware baselines (e.g., RL-TMC or contention-aware list scheduling) and, on the public task graphs, vary the number of machines, CCR, and tier capacities, reporting multi-seed means/variance and runtime overhead.
  5. Please clarify the value network, how the two-level policies are updated with PPO, how rollouts/batches are organized, whether each graph is trained separately, and how actions are selected during evaluation. Please also explain the relationship between the reward design and the final makespan objective under γ=0.99.
  6. Please redraw Figure 1 and standardize figure/table placement.
9 comments
AuthorsOpenReview ↗

Response to Reviewer bqxU (1/6)

Critical Weaknesses: 1.Novelty and positioning need to be sharper. ... However, the experiments do not compare against existing contention-aware schedulers, ... It is therefore difficult to judge the incremental benefit of this combination.

We thank the reviewer for pushing on the positioning. Neither communication‑contention modeling nor the two‑level task/device decomposition is individually novel, and we claim neither: the decomposition appears as early as Lera and Guerrero (2024) [1], and our related work already credits earlier contention‑aware scheduling. As the reviewer identifies, our contribution is their combination — (i) a capacity‑limited tier‑occupancy model, (ii) state‑dependent tier‑estimation features that make this occupancy observable to the policy, and (iii) jointly learned task and machine selection. We have rewritten the contribution statement to say this directly, and expanded the related work section to position the recent learning‑based methods.

This combination is what separates SCHEMA from the closest prior work. Doppler [2] uses a two‑level policy, but its observation carries no representation of link occupancy, so the congestion earlier placements create is invisible at both levels. RL‑TMC [3] models contention but learns only task priorities, delegating processor assignment and message scheduling to a fixed heuristic; contention reaches its policy only through the final makespan, not through what it observes. Among the methods we are aware of, SCHEMA is the first to learn both decisions with contention visible at each.

On comparing against contention‑aware schedulers directly, we looked for RL‑TMC [3] but found no public implementation to reproduce faithfully, and its shared‑bus setting makes its published makespans not directly comparable to our capacity‑limited, multi‑tier one. The incremental benefit of the combination — which the reviewer rightly wants isolated — is exactly what our ablations provide, and more cleanly than a cross‑codebase comparison could. SCHEMA‑NoTier keeps the same two‑level architecture and the same contention‑aware environment and removes only the tier‑estimation features; its makespan rises sharply (Table 4), so the two‑level architecture alone cannot explain the result. Removing the congestion modeling (SCHEMA‑Static) and replacing the hierarchy with a flat policy (SCHEMA‑Flat) degrade it further. Each ablation changes one component with everything else held fixed, isolating its effect.

We acknowledge that the ablations do not stand in for a direct comparison with another contention‑aware scheduler, but they offer controlled evidence for the benefit of the combination. Moreover, to give the contention-aware comparison the reviewer requested, we also implement CA-HEFT, a contention-aware list scheduler. It keeps HEFT’s static upward-rank priorities but chooses each machine by the tiered, capacity-limited memory cost instead of a fixed per-edge cost. These are underway; results will be shared during the discussion period as they become available and included in the revised paper.

We thank the reviewer for the opportunity to make this positioning clearer — the sharpened contribution statement and the expanded related work are a direct result of this comment.

References:

  1. Isaac Lera and Carlos Guerrero. Multi-objective application placement in fog computing using graph neural network-based reinforcement learning. The Journal of Supercomputing, 80(19): 27073–27094, 2024.
  2. Xinyu Yao, Daniel Bourgeois, Abhinav Jain, Yuxin Tang, Jiawen Yao, Zhimin Ding, Arlei Silva, and Chris Jermaine. DOPPLER: Dual-policy learning for device assignment in asynchronous dataflow graphs. In International Conference on Learning Representations, 2026.
  3. Shaima Rahim, Navaneeth V. Sankar, Piyoosh Purushothaman Nair, and Rajesh Devaraj. A reinforcement learning approach to contention-aware co-scheduling in heterogeneous cyber-physical systems. Computer Communications, 257:108616, 2026b.
AuthorsOpenReview ↗

Response to Reviewer bqxU (2/6)

Critical Weaknesses: 2. The DOPPLER baseline adaptation is unclear. ...; SCHEMA constructs task order and machine assignment step by step. ... The use of only a single placement sweep for Placeto also needs justification.

Questions For Authors: 3. How is DOPPLER's device placement converted into the task schedule used by your evaluator? ... What is the rationale for using only a single placement sweep for Placeto?

We thank the reviewer for pressing on the DOPPLER adaptation and on train/test consistency — these are the details that make the comparison trustworthy, and Appendix E has been expanded to give all of them.

DOPPLER [1] follows a two-stage simulation-based training procedure. Stage I uses imitation learning to initialize its policies from heuristic decisions, rather than a makespan-based reinforcement learning reward. Stage II performs reinforcement learning using the makespan-based reward computed by our tiered-contention evaluator. The same evaluator is used during testing. Consequently, DOPPLER's Stage-II training and evaluation are performed under identical contention assumptions, avoiding a static-training/contended-testing mismatch.

From placement to schedule: DOPPLER’s SEL and PLC policies select an operation and its device. From the lowest-cost episode we record the device assignments and SEL’s operation-selection sequence: the assignments become the task-to-machine mapping, and SEL’s sequence becomes the explicit scheduling order supplied to our evaluator. DOPPLER’s original asynchronous runtime fixes execution order at run time; since our evaluator consumes an explicit order, we use SEL’s own selection sequence — the ordering produced by DOPPLER’s policy itself — rather than imposing an external heuristic. We map both back to the original workload identifiers, validate the schedule against DAG precedence, and replay it through the common evaluator without reordering.

Stage III: We omit Stage III, which fine-tunes the policy on real GPU execution through the Einsummable engine. This hardware-in-the-loop step is outside the scope of a simulation study, and including it would give DOPPLER feedback that no other method receives.

Placeto [2] formulates placement as iterative node updates, with an episode containing n∣V∣n|V| decisions, where nn is a tunable number of passes. We use n=1n=1 to control computational cost on large DAGs. Unlike the grouped-operation representation in the original work, our adaptation operates on individual task nodes. Consequently, one pass on MatInv already involves 16,208 placement decisions, while two passes would require 32,416. We acknowledge that additional passes could improve placement quality and identify this as a limitation of our adaptation.

References:

  1. Xinyu Yao, Daniel Bourgeois, Abhinav Jain, Yuxin Tang, Jiawen Yao, Zhimin Ding, Arlei Silva, and Chris Jermaine. DOPPLER: Dual-policy learning for device assignment in asynchronous dataflow graphs. In International Conference on Learning Representations, 2026.
  2. Ravichandra Addanki, Shaileshh Bojja Venkatakrishnan, Shreyan Gupta, Hongzi Mao, and Mohammad Alizadeh. Learning generalizable device placement algorithms for distributed machine learning. In Advances in Neural Information Processing Systems 32, pp. 3983–3993, 2019.
AuthorsOpenReview ↗

Response to Reviewer bqxU (3/6)

Critical Weaknesses: The communication simulator lacks grounding and parameter justification. ... The model lets a transfer occupy a tier until the successor task starts rather than until data transmission completes; ... and validate or analyze the sensitivity of conclusions to parameter changes.

Questions For Authors: 1. How were the parameters in Table 6 obtained? Please provide units, the complete per-link M2M costs, hardware measurements, or a parameter-sensitivity study.

Questions For Authors: 2. Why does a link resource remain occupied until the successor task starts? If data transmission has finished but the task is still waiting for a machine, how is this handled? What is the physical meaning of moving same-machine data to GROUP/GLOBAL when LOCAL is full?

We thank the reviewer for pressing on what the simulator’s rules represent; it lets us make the model’s grounding explicit, and we have expanded Appendix D to state it. The tiers are memory, not link bandwidth or reservations: LOCAL is a small per‑machine memory, GROUP a shared per‑group memory, and GLOBAL the top‑level memory. This settles the two rules the reviewer flags. A datum occupies its tier from when its producer finishes until its last consumer has read it, because it must reside in memory until it is consumed, not merely until it is transmitted; if it has arrived but the consumer is still waiting for its machine, it stays buffered in the tier, occupying capacity, until read. Same‑machine data moves to GROUP or GLOBAL when LOCAL is full — once LOCAL cannot hold another item, the datum is placed in the larger shared or global memory at higher cost, as data spills from a scratchpad to shared memory in a real hierarchy. The resources these rules correspond to are therefore storage buffers and their access cost.

On grounding, the capacities and costs reflect this hierarchy rather than being tuned. Each capacity κt\kappa_t is the number of data items a tier’s memory holds; each per‑unit cost ρt\rho_t is a relative measure of the tier’s access latency and energy, ordered LOCAL - GROUP - GLOBAL, with the M2M cost set per linked pair to capture the Euclidean distance between machines. The costs are relative rather than physical measurements; we have added Table 7 to state this and to list the complete per‑pair M2M costs.

Because the costs are relative, we validate that the conclusions do not depend on their specific values with a sensitivity study — the analysis the reviewer asks for in place of hardware measurement. The policy is trained on the default configuration and evaluated, without retraining, under the capacities and costs scaled across a range, with the heuristics recomputed for each setting as a reference. We will report these results during the discussion period.

Reviewer_XQg9OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

In this paper, the assumption is that we have a dependency graph over tasks and the goal is to assign tasks to machines in the following situation. Machines are joined by an interconnect with several “tiers”, and each tier has a capacity. Presumably T(1, 2) and T(3, 4) (for example) can be overlapping, meaning that the same “tier” can be used to connect machines 1 and 2 and machines 3 and 4. Each tier has a transfer cost (as opposed to speed) rho, and when we send from one machine to the next, we greedily choose the tier with the lowest number and that still has capacity, so that presumably, the lower numbers have lower costs. A “schedule” is an assignment of tasks or vertices in the graph to machines. Presumably the time is then computed via simulation, but the paper does not really say. Greedily assign vertices that have all of their dependencies satisfied to open tiers such that no their is saturated. As tasks finish, they open up tiers and dependencies are fulfilled. The simulation runs to the end, and then the makespan C_max is the last finish time for any vertex. The paper proposes a hierarchical policy (two sub-tasks: choose the next vertex and then place) to learn to do the assignment, using RL. Transformers are used to learn the policies.

Critical strengths

This paper addresses a clear gap in the learned-schedule literature: the current models do not consider the sort of sophisticated, hierarchical communication model with contention considered in the SCHEMA paper. In fact, this is the central contribution of the paper. Figure 2 very nicely demonstrates the gap between a simple communication model (no contention, transfer costs are fixed) and the more realistic communication model demonstrated in the paper. This is a nice contribution.

Table 3 very convincingly demonstrates that it is necessary to take into account contention/congestion during training, if the test environment has this sort of contention. Trained without contention and tested with increases running time more than 75% versus both training and testing under contention.

Experiments are run on graphs that are larger and more challenging than what you usually see in such papers, with up to 16,000 vertices and 45,000 edges.

Critical weaknesses

The hierarchical policy of Section 3.3 appears to be closely related to the dual policy mechanism of Doppler, which used one policy to choose the next vertex in the graph add to a device, and then a second policy to choose a device. True, Doppler differs in other ways, but the dual policy seems to be borrowed directly.

There is no pseudocode for the simulator used to actually cost the graphs. Appendix F does say a bit about the process, but without code it is not possible to know how ties are handled, how waiting on a busy machine is handled. Especially concerning/confusing is the statement in Appendix F that “The platform model traverses the tasks in schedule order while maintaining the evolving platform context.” It is unclear what “in schedule order” means—is this the order in which the tasks were scheduled by SCHEMA? So SCHEMA is effectively able to control the underlying system by choosing the order? No comparisons are “fair” unless the baselines are also able to control the execution order. Which of the baselines also output an order, and did you use that order in the same way as SCHEMA during the experiments? Which baselines did not output an order, and how did you impose ones?

One big concern I have is that each of these papers used as baselines in Table 2 are likely going to have their own simulators and reward models. It’s unclear to me if, to implement the experiments, the authors just dropped in these competitive methods unchanged on the tested graphs, trained using their original rewards structures, testing against SCHEMA’s contention-based cost model. Such a test is not particularly useful—clearly when you train method A trained on cost model 1 on B trained on cost model 2 and then apply B ito cost model 1, you would expect B to to worse than A. In fact, such a comparison is actually harmful because it does not say anything meaningful about A or B (except that B can’t do as well as a natively-trained method such as A) and yet the reader of a paper will somehow assume that placement method A is “better”. It seems that this is exactly what SCHEMA has done, however. The authors write, “The learned schedulers, READYS, Placeto, Doppler, and GDP, are tuned to the setting they were built for and transfer poorly beyond it, which may explain why they trail on every graph” and “What none of the baselines do, heuristic or learned, is account for contention. Each treats the cost of a transfer as fixed and cannot see the contention its own placements create”. Furthermore, Section 4.1 claims the learned baselines are “trained under the same conditions as SCHEMA (Appendix E).” And This seems to indicate that in fact, the learned schedulers are not being trained on the cost model they are tested on (which is the cost model in the paper).

Another issue is the fact that all experiments take place only in simulation, and not on a real system. Yes, the results are still interesting, and yes, the authors are very open about the fact they only test in simulation, but the challenge is that the simulation is so idealized that it may be much easier to learn to optimize for the simulated reward than an actual reward in a real system. The paper would have been much stronger had the RL continued in a real system, or at least, had the authors attempted to see if the learned SCHEMA model transferred to a real multi-node computer system. At the very least, this demands a sensitivity experiment, where the authors train on one simulated setting and then tested on a variety of other settings. Further, the authors should have justified their parameter choices, including the various costs and capacities and the use of infinite GLOBAL bandwidth.

Questions for authors

I think that the biggest single question I have is regarding the choice to train all baselines on the "wrong" cost model---see my "critical weaknesses". Do the authors agree with my concerns? If so, what can be done to alleviate them?

7 comments
AuthorsOpenReview ↗

Response to Reviewer XQg9 (1/4)

Thank you for taking the time to review our paper and provide insightful feedback! We address your concerns as below:

The hierarchical policy of Section 3.3 appears to be closely related to the dual policy mechanism of Doppler, ... True, Doppler differs in other ways, but the dual policy seems to be borrowed directly.

We thank Reviewer XQg9 for highlighting the similarity between SCHEMA and Doppler. We fully agree that the task‑selection‑then‑device‑placement decomposition is an established design choice, used in Doppler [1], in SCALE [2], and in the earlier work of Lera and Guerrero (2024) [3], where two PPO actor–critic policies are trained for sequential task selection and device placement. SCHEMA adopts it only for scalability: on dependency graphs with up to 16,000 tasks, a flat joint task–machine policy fails to learn, as our SCHEMA‑Flat ablation confirms.

SCHEMA’s contribution is therefore not the two-level structure itself, but what this structure operates over: SCHEMA makes communication contention an explicit, dynamic part of the environment that both levels observe and act on. It does so through the capacity‑limited tier model, and exposes this contention to both policy levels through tier‑occupancy features. Thus, both task selection and device placement can account for the congestion caused by earlier placements. This is where SCHEMA departs from Doppler [1]. Doppler learns device placement under a contention‑free cost model, so its placements cannot anticipate contention; SCHEMA selects under live tier occupancy. The difference lies in the environment, not the number of policies.

This is also why Doppler, retrained with the same makespan reward in our tiered environment (Appendix E), still trails SCHEMA in performance: its observation cannot represent the contention the reward reflects. The SCHEMA‑Static and SCHEMA‑NoTier ablations isolate exactly this, each removing SCHEMA’s contention‑awareness while keeping the two‑level structure intact, and both degrade sharply. In the revision we reword the second contribution so the two‑level policy reads as the mechanism rather than a claimed novelty, and state in Section 3.3 and Related Work that the task‑then‑machine decomposition follows prior dual‑policy schedulers, Doppler included, with SCHEMA’s contribution being the contention environment and the features it operates over.

References:

  1. Xinyu Yao, Daniel Bourgeois, Abhinav Jain, Yuxin Tang, Jiawen Yao, Zhimin Ding, Arlei Silva, and Chris Jermaine. DOPPLER: Dual-policy learning for device assignment in asynchronous dataflow graphs. In International Conference on Learning Representations, 2026.
  2. Jierui Lan Zixuan Liang Aiji Liang Xu, Zhifei and Jinxi He. Scale: Scalable cross-attention learning with extrapolation for agentic workflow scheduling. arXiv preprint arXiv:2606.06820, 2026.
  3. Isaac Lera and Carlos Guerrero. Multi-objective application placement in fog computing using graph neural network-based reinforcement learning: I. lera, c. guerrero. The Journal of Supercomputing, 80(19):27073–27094, 2024.
AuthorsOpenReview ↗

Response to Reviewer XQg9 (2/4)

There is no pseudocode for the simulator used to actually cost the graphs. Appendix F does say a bit about the process, but without code it is not possible to know how ties are handled, how waiting on a busy machine is handled.

It is unclear what “in schedule order” means—is this the order in which the tasks were scheduled by SCHEMA? ... No comparisons are “fair” unless ... Which baselines did not output an order, and how did you impose ones?

We thank the reviewer for asking for the evaluator in full; both comments about the missing pseudocode and the ambiguous “schedule order” wording are fair. In the revised PDF, Appendix F gives the full evaluator pseudocode (Algorithm 1) and the corrected “schedule order” wording, and Appendix E specifies the ready‑time ordering rule for the placement‑only baselines.

The evaluator does not independently optimize or rearrange the execution order provided by a scheduling method. Each method outputs, for every machine, the ordered list of tasks assigned to it, and the simulator replays that order: a task starts once its turn on its machine arrives and its predecessors’ data has arrived under the tier model, and start/finish times follow. Because each machine’s order is fully specified by the schedule, no ties arise, and “waiting on a busy machine” means a task waits for the tasks placed before it on that machine to finish. “Schedule order” therefore means the method’s own output, not an order the evaluator imposes.

This is also what makes the comparison fair. Deciding the execution order is not an advantage handed to SCHEMA — it is part of the scheduling problem, and every baseline solves it too. A scheduler must choose both where each task runs and in what order it runs there, and the two decisions cannot be separated. HEFT, PEFT, and IPEFT rank the tasks and place them in that rank; the sequential learned schedulers fix an order as they build their schedules; SCHEMA fixes its order through the sequence in which it selects tasks. The evaluator adds nothing of its own — it replays each method’s order through the same simulator, SCHEMA’s for SCHEMA and each baseline’s for that baseline. Every method is scored on the complete schedule it emits, under identical rules, so SCHEMA holds no control over execution that the baselines lack.

Methods that output only a placement and not an execution order (Placeto, GDP) do not specify an order on each machine. For these we order the tasks on each machine by ready time — the moment all of a task’s predecessors have finished and its input data has arrived — applied identically to both, which is the standard way to turn a placement into an executable schedule.

We thank the reviewer for the chance to make the evaluation explicit; the section is clearer and the fairness of the comparison easier to verify as a result.

AuthorsOpenReview ↗

Response to Reviewer XQg9 (3/4)

One big concern I have is that each of these papers used as baselines in Table 2 are likely going to have their own simulators and reward models ... It seems that this is exactly what SCHEMA has done, however. The authors write ... Each treats the cost of a transfer as fixed and cannot see the contention its own placements create ... And This seems to indicate that in fact, the learned schedulers are not being trained on the cost model they are tested on (which is the cost model in the paper).

This is the most important question about our evaluation, and it deserves a direct answer: no baseline is trained on its own reward and then tested on ours. The reviewer is right that such a mismatch would make the comparison meaningless — and it is exactly the one our setup is built to avoid.

Every learned baseline — READYS, Placeto, Doppler, and GDP — is trained from scratch inside our contention environment, on the same training graphs and machine configuration and under the same realized makespan reward that SCHEMA uses, and each is evaluated under that same cost model. No baseline is trained on its original reward and then tested on ours; there is no train on one, test on another mismatch. Appendix E now states this per baseline, together with the matched training budget and tuning effort.

The confusion came from one sentence — “tuned to the setting they were built for and transfer poorly beyond it” — which we have removed. It was not a claim about training distribution. The point is about representation: these methods are built for settings without endogenous contention, where the cost of a transfer is fixed and known in advance, and their policies carry no representation of link occupancy. Trained in the same contention environment as SCHEMA, they still cannot perceive the congestion their own placements create. The training signal reflects contention; the representation they act on does not. That is why they trail — not because they are evaluated outside the cost model they were trained on.

Moreover, to separate contention‑awareness from architecture, in the ablations SCHEMA‑NOTIER keeps congestion in the environment but removes the tier estimation features from the policy’s input, so the agent is trained and tested under the identical contention cost model yet cannot see which tier a transfer takes. This is the same blindness the baselines have, now inside SCHEMA’s own network. On MatInv its makespan rises sharply and falls into the baseline range, behind the HEFT, PEFT, and IPEFT heuristics (ablation, Table 3). The two‑level attention architecture alone does not explain the result; stripped of contention‑awareness, the same network is no better than a classical heuristic. The advantage comes from making contention observable.

We thank the reviewer for pressing on this; it is the clarification that most improves the paper, and the revised wording together with Appendix E leaves no ambiguity about how the baselines are trained.

Reviewer_an2NOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses the problem of scheduling directed acyclic graph (DAG) tasks in environments with limited machine resources and intense communication contention, proposing a hierarchical reinforcement learning framework named SCHEMA. Traditional schedulers typically assume that the communication cost of moving data between compute nodes is static and known in advance, but in multi-task, highly contended environments, data transfers often collide on the same links, resulting in the actual communication cost depending on the scheduler's own prior task placement decisions. To address this issue, SCHEMA models the scheduling process as a hierarchical Markov decision process and utilizes capacity-limited link tiers to dynamically simulate the communication environment. The policy network employs two-level Transformer pointer networks, introduces the dynamic tier costs as features into the observation, and optimizes the final makespan using the PPO algorithm. Experiments show that across 4 graph structures of varying scales, SCHEMA outperforms 8 traditional and learning-based baseline methods, achieving a performance improvement of up to 29% over the strongest baseline, particularly on the largest workload.

Critical strengths
  1. The paper points out that when machines are scarce, the communication cost is determined by the scheduler's own early placement decisions. By introducing interconnect tiers with capacity limits and varying costs, it successfully integrates the communication contention mechanism into the dynamic environmental modeling.

  2. It designs a hierarchical Transformer policy network that first selects tasks based on the ready set, and then selects target machines based on the available set. This architecture, combined with perception features of the current tier congestion, effectively controls the dimensionality of the action space and maintains inference feasibility when facing tens of thousands of nodes.

  3. Through a series of ablation experiments, the paper proves the independent contributions of the three core components: the congestion-aware environment, the tier estimation features, and the hierarchical policy decomposition. Removing any of these modules for retraining results in a significant drop in model performance.

Critical weaknesses
  1. Among the four datasets used for experimental evaluation, ROBOT and SPEC fpppp belong to classic small-scale benchmarks from around the year 2000 or earlier, which cannot represent modern complex system scheduling requirements. While a performance improvement of up to 29.4% is achieved on the largest graph (MATINV), this dataset is a closed-source proprietary dataset. The lack of modern, large-scale, and open-source datasets weakens the universality of the experimental conclusions and the reproducibility for the community.

  2. The makespan results presented in the tables are all single best results. Considering the inherent variance of reinforcement learning algorithms, the failure to provide means and variances across multiple random seeds makes it difficult to truly evaluate the stability of the algorithm.

  3. The paper relies on engineering design and experimental verification. It lacks optimality or convergence proofs for the hierarchical Markov modeling and the designed reward function.

  4. The final evaluation method is entirely based on simulation functions, and sets a fixed 2D grid multi-core interconnect structure and specific tier escalation logic, without conducting end-to-end performance verification in real distributed hardware clusters and broader interconnect architectures.

Questions for authors
  1. Given that the first three datasets in the experiments are relatively old, and the large MATINV dataset cannot be open-sourced due to confidentiality reasons, can the authors conduct supplementary experiments on existing newer and open-source large-scale datasets?

  2. Reinforcement learning is quite sensitive to random seeds. Are the makespan results in Tables 2 and 3 the results of a single run or the optimal values under multiple random seeds? Can you supplement the mean and variance data based on multiple independent random seeds to prove the stability of the algorithm's performance?

  3. Can you provide some theoretical proofs and analyses regarding the designed reward function or the overall effectiveness and optimality of the algorithm?

  4. How are the hyperparameters such as κt\kappa_t and ρt\rho_t set in SCHEMA? How do they affect the performance of the method?

7 comments
AuthorsOpenReview ↗

Response to Reviewer an2N (1/4)

We appreciate the time and detail the reviewer put into this review. Our responses to each concern follow.

Critical Weaknesses: 1. Among the four datasets used for experimental evaluation, ROBOT and SPEC ... The lack of modern, large-scale, and open-source datasets weakens the universality of the experimental conclusions and the reproducibility for the community.

Questions For Authors: 1. Given that the first three datasets in the experiments are relatively old, and the large MATINV dataset cannot be open-sourced due to confidentiality reasons, can the authors conduct supplementary experiments on existing newer and open-source large-scale datasets?

We thank the reviewer for pressing on reproducibility; it is a fair concern, and it has prompted us to make MatInv public, which makes the entire evaluation open. ROBOT and SPEC are standard public benchmarks, and GEMM is public with its construction documented in Appendix C, so MatInv was the only closed graph. What makes it confidential is its origin, not its scheduling content: the task graph, its dependencies, and the per‑node computation and per‑edge communication volumes carry no proprietary information. We release exactly this as an anonymized DOT file, provided in the supplementary material, so every graph in the evaluation, including the largest, is now openly available and reproducible.

Moreover, on the age of ROBOT and SPEC, recency matters for many kinds of data, because the distribution they capture shifts over time. A task‑dependency graph is not like that. It is a DAG of computation and communication, and its difficulty is set entirely by its structure — size, width, critical‑path depth, how many tasks are ready at once, and the balance of communication to computation. None of these fades with age, and a structurally demanding graph is as hard to schedule today as on the day it was written. The spread of our graphs is deliberate: ROBOT and SPEC at the small end, GEMM and MatInv at the large end, chosen to show that SCHEMA holds across the full range of scales — and that its advantage widens on the largest, most contended graphs, where scheduling is hardest. What the evaluation rests on is this breadth of sizes and shapes, not the vintage of any single graph.

AuthorsOpenReview ↗

Response to Reviewer an2N (2/4)

Critical Weaknesses: 2. The makespan results presented in the tables are all single best results. Considering the inherent variance of reinforcement learning algorithms, the failure to provide means and variances across multiple random seeds makes it difficult to truly evaluate the stability of the algorithm.

Questions For Authors: 2. Reinforcement learning is quite sensitive to random seeds. Are the makespan results in Tables 2 and 3 the results of a single run or the optimal values under multiple random seeds? Can you supplement the mean and variance data based on multiple independent random seeds to prove the stability of the algorithm's performance?

We thank the reviewer for raising this; reporting variance across seeds is the right way to show stability, and it is what we are adding. The numbers in Tables 2 and 3 are each from a single training run, not the best across several seeds — there is no selection over seeds.

We are retraining SCHEMA and every learned baseline across multiple independent seeds and will report the mean and standard deviation of their makespans in Tables 2 and 3 during the discussion period, so every learned method in the tables carries a mean and standard deviation. The deterministic heuristics (HEFT, PEFT, IPEFT) have no seed dependence and are reported once.

AuthorsOpenReview ↗

Response to Reviewer an2N (3/4)

Critical Weaknesses: 3. The paper relies on engineering design and experimental verification. It lacks optimality or convergence proofs for the hierarchical Markov modeling and the designed reward function.

Questions For Authors: 3. Can you provide some theoretical proofs and analyses regarding the designed reward function or the overall effectiveness and optimality of the algorithm?

We thank the reviewer for pressing on the theoretical grounding; it prompted us to state the reward and MDP properties formally rather than leave them implicit. We are also precise about the part no method in this space can claim: full global‑optimality or convergence guarantees do not exist for any deep‑RL scheduler over an NP‑hard combinatorial problem, but it can be shown that the reward is aligned with the true objective by construction and that the policy structure introduces no approximation.

The reward is a potential‑based shaping of the makespan objective, with potential Φ(s)=−Cmax⁡(s)/N\Phi(s) = -C_{\max}(s)/N and rk=Φ(sk)−Φ(sk−1)r_k = \Phi(s_k) - \Phi(s_{k-1}). At γ=1\gamma=1, by the potential‑based shaping theorem [1] this leaves the optimal policy unchanged, and the shaped return telescopes exactly to −Cmax⁡/N-C_{\max}/N, so maximizing the undiscounted return is identical to minimizing the final makespan. Training uses γ=0.99\gamma=0.99, a near‑one discount that lowers update variance and optimizes a close surrogate of this objective. We add this as a short proposition.

On optimality of the schedule itself, DAG scheduling under communication contention is NP‑hard, so no efficient method — learned or heuristic — can guarantee an optimal schedule; the appropriate measure is quality against strong baselines, which the experiments report. The two‑level policy is not an approximation of a joint policy but an exact rewriting of it, as the product of the task policy and the machine policy conditioned on the selected task. On convergence, SCHEMA is trained with PPO, whose clipped surrogate gives the standard monotonic‑improvement basis for policy‑gradient methods [2]. We are currently training each configuration across multiple seeds and will report the mean and standard deviation of the makespans during the discussion period, documenting how reproducibly training converges.

The revision states these properties explicitly in section 3 Method: the reward’s shaping invariance and the γ=1\gamma=1 identity (with the γ=0.99\gamma=0.99 surrogate) as a short proposition, and the exact two‑level decomposition where the policy is defined — so the design rests on stated properties, not engineering alone.

References:

  1. Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the Sixteenth International Conference on Machine Learning (ICML), pp. 278–287, 1999.
  2. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017

Comments on the paper

2 comments

Dear Reviewers,

The authors have provided rebuttals to your review. Could you please check their responses and provide any further feedback or questions for the authors to address at your convenience?

Thank you for your time and contribution.

Regards,

AC

AuthorsOpenReview ↗

Summary of Revisions and New Results

Dear Area Chair and Reviewers,

We thank the reviewers for their thorough and constructive feedback, and the Area Chair for overseeing the discussion. The revision answers every concern raised, and the new experiments substantially strengthen the paper's central claim: SCHEMA's advantage comes from making contention visible to the policy, and it holds across seeds, baselines, and platforms.

New evidence

  • Against a contention-aware scheduler. CA-HEFT, a contention-aware variant of HEFT, is now in Table 2. On MatInv, SCHEMA's makespan is 28.4% below it. Since CA-HEFT itself accounts for contention, this shows that SCHEMA's gain comes from handling contention better, not only from modeling it.
  • Across platforms. A new sensitivity study (Appendix G) varies tier capacity over an 8-fold range without retraining, and machine count from 8 to 32. SCHEMA outperforms CA-HEFT in all seven configurations, and its margin grows as the platform offers more capacity to exploit and spans more groups.
  • Across seeds. All learned methods and ablations now report mean ± standard deviation over five seeds (Tables 2 and 3). SCHEMA is stable, with a standard deviation of 2–8% of its mean, and improves on the strongest baseline by 18.2% ± 7.0% on MatInv.
  • Each component, on public data. The five-seed ablations, now also run on the public SPEC fpppp graph, show that every component contributes on both graphs; on MatInv, removing any one raises makespan by 51–62%.
  • At practical cost. Appendix H reports training and scheduling time: on MatInv, SCHEMA trains faster per episode than Doppler, READYS, and Placeto, and schedules within the time range of the classical heuristics.

Clarifications and openness

  • Fully reproducible. MatInv is released as an anonymized DOT file, so all four evaluation graphs are public.
  • Fair comparison. Every learned baseline is trained from scratch in the same contention environment, with the same reward; each adaptation, including Doppler's and Placeto's, is specified in Appendix E.
  • Grounded simulator. Appendix D grounds the platform in a CGRA memory hierarchy, and Appendix F gives the full evaluator pseudocode and its validation against a SystemC/TLM hardware model.
  • Formal properties. Section 3 now states, as a proposition, that the shaped reward is aligned with the makespan objective, and that the two-level policy is an exact decomposition of the joint policy.
  • Presentation. Figure 1 is redrawn as a vector figure, placement is standardized, and the contribution statement and related work are sharpened.

We are grateful for the reviewers' engagement, which has made the paper considerably stronger, and we are happy to answer any further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.