LayerDAG: A Layerwise Autoregressive Diffusion Model for Directed Acyclic Graph Generation
Authors: Mufei Li
Viraj Shitole
Eli Chien
Changhai Man
Zhaodong Wang
Srinivas
Ying Zhang
Tushar Krishna
Pan Li
Venue: ICLR 2025 Spotlight (2025)
Keywords: directed acyclic graphs
graph generation
discrete diffusion
autoregressive model
Primary area: learning on graphs and other geometries & topologies

Abstract: Directed acyclic graphs (DAGs) serve as crucial data representations in domains such as hardware synthesis and compiler/program optimization for computing systems. DAG generative models facilitate the creation of synthetic DAGs, which can be used for benchmarking computing systems while preserving intellectual property. However, generating realistic DAGs is challenging due to their inherent directional and logical dependencies. This paper introduces LayerDAG, an autoregressive diffusion model, to address these challenges. LayerDAG decouples the strong node dependencies into manageable units that can be processed sequentially. By interpreting the partial order of nodes as a sequence of bipartite graphs, LayerDAG leverages autoregressive generation to model directional dependencies and employs diffusion models to capture logical dependencies within each bipartite graph. Comparative analyses demonstrate that LayerDAG outperforms existing DAG generative models in both expressiveness and generalization, particularly for generating large-scale DAGs with up to 400 nodes—a critical scenario for system benchmarking. Extensive experiments on both synthetic and real-world flow graphs from various computing platforms show that LayerDAG generates valid DAGs with superior statistical properties and benchmarking performance. The synthetic DAGs generated by LayerDAG enhance the training of ML-based surrogate models, resulting in improved accuracy in predicting performance metrics of real-world DAGs across diverse computing platforms.

Published as a conference paper at ICLR 2025
LAYERDAG: A LAYERWISE AUTOREGRESSIVE DIFFU SION MODEL FOR DIRECTED ACYCLIC GRAPH GEN- ERATION
Mufei Li", Viraj Shitole', Eli Chien', Changhai Man', Zhaodong Wang", Srinivas Sridharan', Ying Zhang' Tushar Krishnal, Pan Li'
Georgia Institute of Technology. (mufei. li, viraj2, ichien6, cman8, sanlifegatech.ede edu Meta, Izhaodongwang, zhangying) (ecriing@mmtt...mmm @meta.com NVIDDA, srisri raaran@nvidd com Georgia Institute of Technology, tushardece www.ecce.gatcch.e...
ABSTRACT
Directed acyclic graphs (DAGs) serve crucial data representations in domains such as hardware synthesis and compiler/program optimization for computing sys- tems. DAG generative models facilitate the creation of synthetic DAGs, which can be used for benchmarking computing systems while preserving intellectual property. However, generating realistic DAGs is challenging due their inherent directional and logical dependencies. This paper introduces LayerDAG, an au- toregressive diffusion model, to address these challenges. LayerDAG decouples the strong node dependencies into manageable units that can be processed sequen- tially. By interpreting the partial order nodes as a sequence of bipartite graphs, LayerDAG leverages autoregressive generation to model directional dependencies and employs diffusion models to capture logical dependencies within each bipar- tite graph. Comparative analyses demonstrate that LayerDAG outperforms exist- ing DAG generative models in both expressiveness and generalization, particularly for generating large-scale DAGS with up 400 nodes-a critical scenario for sys- tem benchmarking. Extensive experiments on both synthetic and real-world flow graphs from various computing platforms show that LayerDAG generates valid DAGs with superior statistical properties and benchmarking performance. The synthetic DAGS generated by LayerDAG enhance the training of ML-based sur- rogate models, resulting in improved accuracy in predicting performance metrics real-world DAGs across diverse computing platforms. Our implementation is available
INTRODUCTION
A Directed Acyclic Graph (DAG) is a data structure that represents the order of elements (Bang- Jensen & Gutin 2008). Unlike linear sequences, which follow single, straight path from the first to the last element, DAGs incorporate branching and merging, allowing for the modeling of complex dependencies and hierarchies. This flexibility makes DAGs ideal for representing diverse problem
domains such as workload behavior during system execution Sridharan et al. (2023), operator de- pendence for program analysis (Phothilimthana et al. 2023b [uo et al. 2021 [ Cortez et al., 2017 dataflows in circuits (Dong et al.) 2023). task dependencies in project management (Skienal 2008
Borenstein| 2000), and cause-effect relationships (Pearl 1995 Tennant et al. 2020). Additionally, DAGs have recently been used to create challenging benchmarks for evaluating the reasoning capa- bilities of large language models (Zhu et al. 2024).
Despite the benefits of DAGs mentioned above, it is non-trivial to get largescale datasets of real DAGs to enable analysis and optimization. Taking workload execution as an example, DAGs cap- turing execution behavior can help engineers gain valuable insights into performance metrics such

---

Published as a conference paper at ICLR 2025
Logizal Dependence-
infone Ei parths grapt
Dl!ssiin
Carerada wech
the raddec
Logical Dependence- opersiion
noche sttiitute
odget
Directional Depandence-
Hdlga in lipurtin gruph 6
sohrmantaky
Figure 1: (a) A real-world DAG (the computation flow for transformer layer (Vaswani et al. 2017) encompasses complex logical and directional dependencies. Examples of logical dependencies in- clude 1) dimension matching in matrix multiplications and 2) exactly two matrices pointed to a x operation. One example of directional dependencies here is SOFTMAX(QK)V being computed af- ter QK. (b) Each DAG has a unique layerwise partition, an ordered partition of nodes/edges into a sequence of bipartite graphs. In LayerDAG, each bipartite graph G(++) is generated by diffu- sion model conditioned on G(S), LayerDAG generates in order the number of new nodes, their attributes, and the new edges.
as latency and resource consumption exhibited by candidate systems (Luo et al., 2021: Cortez al,) 2017) to optimize the software and hardware accordingly. However, collecting a workload execu- tion DAG (Sridharan et al. 2023) for even a single Large Language Model training job, potentially involving trillions of operations, extremely prohibitive given the size of modern Al platforms. For example, Meta's ' Llama3 was trained on a 24K GPU platform (Dubey et al. (2024) while xAI is build- ing 100K GPU platform. Moreover, few companies in the world even have access platforms of this scale. Even if such a large workload execution DAG could be collected, practical constraints such the storage requirements of the DAGs, and potential to leak private information about the AT model architecture or the training platform configuration further limits DAG sharing. Furthermore, representative and smaller graph is more effective for most performance optimization tasks.
This work focuses on developing generative models for DAGs. We believe this can solve several challenges. First, being able to be data-driven and generate representative small of DAGs can be much more compute and memory efficient than a real DAG given repetitive patterns. Second, this could enable data sharing without compromising intellectual property (Gao al.) 2024| Lin al.) 2020), thereby promoting software and hardware co-design among different companies (Sridharan al. 2023). Third, conditional DAG generative model can efficiently search the space of valid DAGS for optimization purposes in scenarios such as circuit design (Takagi 1999 Dong et al. 2023), ooppmizattti
compiler optimization (Aho et al. 2006 Phothilimthana et al. 2023b), and neural architecture search
(NAS) Zhang et al. 2019 Li et al. 2023a| An et al. 2023).
Serving as an abstraction for flows and node dependencies, DAGs pose significant challenges in de- veloping powerful and efficient generative models due their intrinsic strong directional and logical dependencies, such as control flows, logic gates, and dimension requirements of matrix operations (as illustrated in Fig. [ (a)). These complexities ing a unique combination of challenges regarding both scale and logical rules. In contrast, although social networks may be large in scale, they do not exhibit strong dependencies between nodes and edges. At the other end of the spectrum, molecular graphs, whose generation has also received much interest recently, must adhere chemical rules but are generally smaller in size.
further magnified in large-scale DAGs, present-
This work proposes the use of autoregressive diffusion models to generate DAGs, aiming to decou- ple the strong node dependencies in DAGs into manageable units and handle them sequentially. Our model, named LayerDAG, is based on novel perspective of DAGs: as illustrated in Fig. [ (b), the partial order of nodes dictated by the DAG structure can be decoupled as sequence of tokens, each corresponding to a bipartite graph. This perspective enables the natural modeling of directional dependencies in DAGs through autoregression, and the rest is to address the logical dependencies within a set of nodes incomparable (i.e. no ordering relations) according to the partial order in each autoregressive step, where we leverage diffusion models known for effectively capturing multidi- mensional dependencies (Rombach et al.) 2022 Vignac et al. 2023a). Specifically, the diffusion model is conditioned on previously generated bipartite graphs to generate the next bipartite graph consisting of node attributes and edges.
2

---

Published as a conference paper at ICLR 2025
Li jet al. 2023a An et al. (023). Methodologically, although autoregressive models have been adopted by D- DAV (Zhag et al. 2019) and GraphPNAS (Li et al. 2023a) for DAG generation, they treat either a single node or a node set of constant size as a token. This tokenization method imposes an order between nodes that should be incomparable in the partial order, violating the inductive bias inherent in the DAG structure. We argue that the violation may hurt the generalization capability of generative models. Moreover, D-VAE suffers from a potentially slow generation process by generating one node per iteration. Although GraphPNAS generates multiple nodes per iteration, uses a mixture of Bemoulli distributions to model intra-set edge dependencies, which is less expressive than diffusion models (Wang et al. 2023 Pearce et al.] 2023). DiffusionNAG (An et al.) 2023) employs diffusion models to generate only node attributes given DAG structure. Diffusion models have been used to generate undirected graphs (Niu et al. 2020 Jo et al., 2022; Vignac ct al. 2023a), but they ignore the directional information in DAGs, while our work demonstrates the necessity of the autoregressive component in modeling directional dependencies in DAGs.
Our model advances existing DAG generative models in multiple aspects (Zhang et al. 2019
From the application perspective, all the existing works Zhang et al. 2019 2019 al. 2023a An et al, 2023) focus generating small DAGs (with #nodes I 24) for NAS, while model capable of generating much larger flow graphs (up to ~ 400 nodes) for system/hardware benchmarking. Overall, our work is the first to use autoregressive diffusion models for DAG generation, aiming to take the advantages of both autoregressive models and diffusion models to model the strong dependencies commonly in DAG data.
We conduct extensive experiments to verify the effectiveness of our model. To assess the model's ability learn strong directional and logical rules, we construct a challenging synthetic DAG dataset with injected dependencies for evaluation. Additionally, we employ three real-world datasets- computational graphs on Tensor Processing Units (TPU). flow graphs on Field Programmable Gate Arrays (FPGA), and neural architectures deployed on edge devices- for computing system bench- marking applications. Fach dataset contains thousands of DAGs, with individual DAGS comprising up to hundreds of nodes. We compare the validity and statistical properties of the synthetic DAGs generated by our model with baselines. To measure benchmarking performance, we use the synthetic labeled DAGs to train surrogate machine learning (ML) models to predict TPU runtime, FPGA re- source usage, and the inference latency of neural architectures for the three application scenarios. These trained surrogate models are then applied to the real-world DAGs for testing. Note that ML- based surrogate models are widely used today to measure the performance of systems and programs without the need for time-consuming simulations (Adams al. 2019 Chen et al. 2018 Mendis
et al.
2019:
[ykkora et al. 2022 Steiner et al.] 2202 Baghdadi et | ZZeng et al. 2020 Li
al.
2020 Ahn et al.| 2020 Dubach et al.] [007]] Jia al.J 2020) Kaufman al. [202]] Cao a
2023
Phothilimthana et al. 2023b). We compare the predictions given by the surrogate models
with the ground-truth behavior of the DAGs on the corresponding systems. Results show that the surrogate models trained on our generated synthetic DAGs consistently outperform the ones derived with baseline generative models. We also evaluate the extrapolation and interpolation properties of LayerDAG by generating DAGs with labels out of the regime used for training, and LayerDAG demonstrates a superior generalization capability.
PRELIMINARIES AND BACKGROUND
(1, DAG generation DAG is directed graph without cycles G - (V, X), where V= (1,-... ,N} is the node set, & = f.... , (u, v),- } is the set of directed edges, X is the node attribute matrix. The edge list & can also be equivalently represented as the adjacency matrix A. From a collection of DAGs {G.); ~ Pg. we aim to learn IP with generative model IPg. where 0 denotes model pa- rameters. Additionally, many real-world applications, especially computing system henchmarking, involve labeled DAGs {GG,, 3: where the labels indicate the performance of the corresponding computing systems. DAG generation conditioning on these labels is also of interest, i.c., learning the distribution Pop.
Discrete denoising diffusion While our framework is compatible with various diffusion models, adopt Discrete Demoising Diffusion Probabilistic Model (D3PM) (Austin et al. 2021 as a proof of concept. We briefly review it here. D3PM (Austin et al. 2021] generalizes Multinomial Diffu- sion (Hoogehoom et al. 2021bb in extending DDPM (Ho et al. 2020) to discrete data. D3PM has
3

---

Published as a conference paper at ICLR 2025
two phases, a forward diffusion process and reverse process. Let each entry of ( {0, [0,1] M Mxc be a one-hot encoding of a categorical attribute with C possible values.
The forward process uses T consecutive steps to progressively corrupt (0) - z - into purely random variables Z where Z can be drawn from prior categorical distribution. To corrupt (4) into (t++),, it computes and samples from conditional distribution (Z((+1)) (
Z (1+1, where Q(++1) RCCC is pre-determined transition matrix. A denoising network do is trained to predict the uncorrupted data Z: from (Z(0, f). During the reverse generation process, the trained denoising network is used to convert Z drawn from the prior distribution into realistic data. DiGress (Vignac et al. 2023a) extends D3PM for molecular graph (undirected) generation by treating the presence absence of an edge between node pair binary attribute. The denoising of node attributes and edges takes the form of node classification and link prediction, respectively.
3 METHODOLOGY
In this section, we present the LayerDAG framework. We first describe novel view of DAGs, which uniquely transforms a DAG into a sequence of bipartite graphs. This naturally leads to a layerwise tokenization for autoregressive generation, which tackles the directional dependencies in DAGs. In each autoregressive step. we introduce a layerwise diffusion model that is capable of modeling the dependencies between nodes that are incomparable (no by-default order). We also discuss why our way of DAG decomposition is crucial for model generalization. Lastly, as bipartite graphs across different layers hold different levels of complexity, we also propose flexible quality- efficiency trade-off strategy that adjusts the number of diffusion steps based on layer index.
3.1 UNIQUE SEQUENTIAL VIEW OF DAGS
The structure of DAG essentially establishes partial order among its nodes based on reachability through directed paths. A partially ordered set can be transformed into an ordered sequence while preserving compatibility with the partial order, known
linear extension a topological ordering in the context of DAGs (Kahn 1962, Tarjan 1972). Previous competitive autoregressive models of DAGs utilize this sequential nature generate nodes one at a time following topological order- ing (Zhang et al. 2019). However, topological orderings are not unique. This may compromise the model's 's effectiveness and efficiency. We leave dedicated discussion about the issue to Section 3.3 On the other hand, aon-autoregressive models like diffusion models may be sub-optimal for not explicitly modeling the sequential nature of DAGs.
We map DAGs into unique sequence by extending topological orderings from sequence of single- ton subsets to general subsets. A DAG guaranteed to have a set of source nodes, i.e., the nodes are not destinations of any edges, and we denote them by V(1), Iteratively, we take D(++) c V V(E!) to be the set of nodes whose predecessors are in v(S!), : where y(E)) = -U y(O_ An implied property is that for each v E y((+1), there exists u E y(!) such that (u, v) E E. In addition, for each u E D(),, the longest path from source nodes to it has a length of [ 1. It follows that (V(1), D22) ..., ,)(()) forms an ordered partition of > the moment (L++1) = (Fig. (b)). We refer to p(i,, p()..... ....... (LL) ...) as layers and as the number of layers. For each layer depth < L-1, we also take g(++) = {(u,w) w) E Elu E ViS!) v E y((+1),, }. and (8(2), dered partition of E. This layerwise partition naturally extends arbitrary node and edge attributes. Furthermore, this way of construction is unique and allows reconstructing the original DAG from the sequence (D()), (V(S1) U y(2) g(2), ... (V(SL-1) U V(L) E(L))). where (D(SOVy(+)) g(+1) is bipartite graph whose edges point from one part to another part. Such invertible process of converting a raw data sample into a sequence is known as tokenization in the context of genera- tive models, with notable examples being subwords for language models (Sennrich al. 2016) and patches for image generation (Peebles Xie 2023). Essentially, layerwise partition leads to a layerwise tokenization for DAGS.
g forms an or-
4

---

Published as a conference paper at ICLR 2025
3.2 LAYERDAG
Autoregressive generation The layerwise tokenization motivates the following factorization for probability distribution P (G) of DAGs. Let G = (V.X,A) be a DAG, In analogy to v(O) and v we define ((), X x(S), A (), and A (S)) In addition, we define GOO) (V"), (9) A (1) and
G(S = (Vis), X (E)) A (2 Then, we have
L-1 P (((+)))
P(G)= II t=0
G(S))
L-1
II t=
P (pit+t)) ((50) p (111) ((s)) pu- IP (A ((+1) (Ait))
((S)) x x(*1))
This factorization naturally leads to a layerwise autoregressive generation framework. Iteratively, to generate the (1 + 11th layer, first predicts the number of new nodes with pa (IV(++2) |
Then it generates the node attributes with pa (x((+1) G(St, |)(++)). Finally, it generates the edges with pe (A(++)) G(S), ((+))). The generation process terminates when [ is pre- dicted to be O. All the above generation processes will be conditioned on the previously generated
DAGs G(SO, With layerwise autoregressive generation, this framework potentially allows better generalization to unseen values of L during generation (layer generalization).
Layerwise dfffusion-based generation To preserve the uniqueness of the layerwise tokenization, we need to generate the set of node attributes and edges in the bipartite graph G((+1 as a whole by modeling pe (X(++) G(SD) [)(+1))) and pe (A [1+1]] G(S"), X ((++)) as set-level generations. This requires capturing complex dependencies between the node attributes and edges in the sets, which is crucial for applications like system and circuit design, where strict logical rules are preva- lent, and rule violations can accumulate and propagate over layers of generation. To tackle this issue, we adopt diffusion models for multiple rounds of set refinement in the generation of G(++), We employ two separate diffusion processes for node attribute (I+1) generation and structure (1+1) generation, as suggested by Li al. (Li al., 2023b). For simplicity, we focus on categorical node attributes in this work, which find abundant real-world applications like operator types in computa- tional graphs, and thus adopt D3PM (Austin et al. 202T). Our approach can be extended to handle real-valued attributes by combining discrete diffusion with continuous diffusion, as demonstrated in previous works (Vignac et al. 20236 Hua al. 2024). For more details on layerwise diffusion, see Appendix A
Implementation For different /'s, all modules ([y(I+1)) | G(SO), (X(++) G(S!), p(l+1i),
and ps (A(++) G(S)) ()) share the same parameter 0, which involves DAG encoder. We use an off-the-shelf bidirectional message passing neural network (BiMPNN) (Wen et al. 2020). A single BiMPNN layer updates node representations with synchronous message passing over both A.Wwaaaddd
the directed edges and their reversed counterparts: a (AHW forward + A H reverse + HW selr), where a non-linear layer, H is the node representation matrix, and W's are learnable weight matrices. Both layer size generation pe (IV(+)) ((SD) and node attribute generation po (X+ G(SD), p)(+1)) involve computing graph representations with set pooling operator over the updated node representations. Let (1+1,)) be the node attributes sampled for the (1 1)th layer at the step t in the reverse node attribute diffusion process. After encoding (G(51), .t) into a
context vector ((5)) the denoising network d0x augments the representations of (I+1.)) by ((()) and then applies a transformer without positional encodings (Vaswani et al.] 2017) over them for predicting the set of ((+1), Similarly, the denoising network Φe, for edge diffusion augments (G(S), t) by (x(+1), A (1+.9) for computing the node representations of ((S++)), To predict the probability of edge (u, v) for u E y(s!) and e E y(++1), concatenates and transforms the repre- sentations of node u, node v, and with an MLP.
Training The training process aims to maximize the log- ligelikklihoo of observed graphs under our model. We decompose this objective to train the three modules independently. To account for the autoregressive nature of our approach, we train all modules with teacher forcing. In each training iteration, we randomly sample real partial DAG up / layers and train the model to predict the +
5

---

Published as a conference paper at ICLR 2025
1-th layer. For given partial DAG, the training of pe (10(+11 | G(S)) is analogous to the standard
supervised training of graph classification model. The training of po (x G(S!) |)++1)) and po (A (1+1) G(St), ,( x(+1)) follows the established practices for discrete diffusion models, where the modules are optimized by recovering corrupted discrete data.
Sampling The sampling process follows an autoregressive approach, performing layerwise graph generation. Starting with an empty graph G(SD), we iteratively sample the number of nodes |)(++) for each subsequent layer using Pe ([V++D1 G(S9). [y+++)]
|| is non-zero, we sequentially gen- erate node attributes ((+1) and edges A (1+1) using their respective reverse diffusion processes. We then update G(S++1) with the new nodes, attributes, and edges. This process continues until we predict | +++ to be 0, at which point generation terminates.
Conditional generation LayerDAG is also capable of performing conditional generation. Given labeled DAG (G, y), we train LayerDAG to learn the conditional distribution P(G|Y) by integrating the sinusoidal embeddings of y into the representations of ((!) for any Once trained, the model generate DAGS conditioned specified target properties.
3.3 PERMUTATION INVARIANCE AND MODEL CENERALIZATION
A critical issue in developing probabilistic generative models of graphs is permutation invariance, whether the probability for model to generate a graph is invariant to the particular choice of node ordering. Non-permutation invariant models, such autoregressive models that generate one node at time, require data augmentations with random node orderings during training (You et al. [2018] ei al. 2018). To sufficiently train the model, one has to enumerate a large number of orderings, which could be exponential in N. LayerDAG is permutation invariant with the aforementioned implementation. By aligning with such an inductive bias, LayerDAG has the potential of holding a good generalization capability with limited computational resources for training.
Proposition 3.1 (permutation invariance of LayerDAG) For any depth I, pa (pol+t) G(S)), pe (X+++) G(S0, ()(+2))) and pe (A+11) ((S!), ( are permutation invariant. Hence, LayerDAG is permutaaiin invariant.
Bidirectional MPNN layers are permutation equivariant, and sum and mean pooling op- erators are permutation invariant. (G(+))))))) (G(()) =P (G(++) G(S"), where l1(+1) corresponds p(++) and
follows that for any permutation TI, we have
(S!)) corresponds to v(s), Finally, IP (G) = IT P (G )) G(S)) is also permutation invari- ant.
3.4 FLEXIBLE QUALITY-EFFICIECCY TRADE-OFF WITH LAYER-INDEX-BASE DENOISING SCHEDULE
Note that as / increases, both [)(ST) and [g(++)] increase in general, resulting in more complex edge dependencies. To effectively handle this pattern, we introduce a non-uniform denoising schedule for better allocation of the time budget. Specifically, propose to set the total number of denoising steps for a layer to linearly increase in (.
T Tmin + [[Tmax Tmin) min (1/Lmax- 1}.]
where Tinn <. Tmax are the minimum and maximum number of denoising steps and allow users to make flexible quality-efficiency trade-off for DAG generation with LayerDAG. / the current layer index, Luuxx is the maximum number of layers in the training data, and [+] is the floor function.
The key assumption is that more complex patterns emerge as the layer depth increases, such as long range dependencies between pair of layers with big difference in layer depth, which calls for the use of more denoising steps. When this does not hold, as in the scenario trees with stationary layer distributions, this lased linear denoising schedule will not be useful.

---

Published as a conference paper at ICLR 2025
4 RELATED WORK
We have already extensively compared LayerDAG with DAG generative models. Here, we review relevant undirected graph generative models.
Autoregressive models. GraphRNN (You et al. 2018 and DeepGMG (Li al., 2018) are node- wise autoregressive models for undirected graphs, generating one node at time. D-VAE extends this approach for DAGs and adopts topological orderings (Zhang et al. 2019). For efficiency con- siderations, GRAN proposes sequentially generating node sets of constant size (Liao et al.) 2019). GraphPNAS extends this approach for attributed DAG generation (Li et al. 2023a). Like their DAG counterparts, GraphRNN and GRAN also violate the inductive bias by imposing an order of the nodes. Consequently, they may suffer from inferior effectiveness or training efficiency.
Diffusion models. Niu et al. applies continuous diffusion models to adjacency matrices of undi- rected graphs (Niu et al. 2020). GDSS extends the previous approach to attributed graphs like molecules (Jo et al.] 2022 DiGirsss proposes discrete diffusion model for attributed graph gener- ation (Vignac et al. 2023a). GraphMaker extends DiGress for generating large attributed graphs (Li eet al., 2023b). All these models use a constant number of denoising steps in the generation of the whole graph, regardless of their size and complexities. Recently, there has been an arising interest in exploring the intersections of autoregressive models and diffusion models. TimeGrad (Rasul al.) 2021 proposes an autoregressive diffusion model for time series forecasting. ARDMs (Hoogeboom al. 2021a) generalize order-agnostic autoregressive models and absorbing discrete diffusion. For undirected graph generation, EDGE (Chen et al. (023) and GRAPHARM (Kong et al. (023) pro- pose diffusion models where each denoising step generates a new set of edges and therefore also corresponds to exactly one step in autoregressive generation. Unlike LayerDAG, they do not per- form multiple rounds of refinement, which critical for capturing logical dependencies among node attributes and edges. In contrast, with autoregressive layerwise diffusion, LayerDAG allows for multiple-step refinement in each layer generation, and with the layer-index-basee denoising sched- ule, LayerDAG also allows for using more denoising steps for more complex layers, which provides the overall freedom to balance quality and efficiency.
5 EXPERIMENTS
The end application scenarios of DAG generative models pose multifaceted requirements that mo- tivate the design of our empirical studies. Q1) Given that real-world DAGs encompass complex logical and directional dependencies, where violations can directly invalidate generated samples, how effectively can LayerDAG capture these dependencies by learning from valid DAGs? Q2) Beyond ensuring validity, the application of synthetic data for system and hardware benchmarking necessitates the preservation of correlations between DAGs and system metrics such as throughput, latency, and memory footprint. How effectively can LayerDAG perform DAG generation condition- ing on these metrics to meet these requirements? workloads, including foundation models and edge computing, system vendors need to proactively design next-generation platforms. A model capable of simulating workloads with hypothetical met- rics (e.g. low latency low power consumption) holds significant potential. Additionally, optimizing DAG properties for scenarios like circuit design demands generalization to unseen property values. Thus arises a crucial question: can LayerDAG generalize to unseen regimes of DAG labels when generating DAGs? Q4) Different application scenarios require varying trade-off's between genera- tion efficiency and quality. How effectively does a layer-index -ased denoising schedule (in Sec. 3.4 meet this requirement using a single trained LayerDAG model?
Q3) With the rapid advancements in computational
Baselines We consider three non non-diffusioo autoregressive basclines GraphRNN, D-VAE, and GraphPNAS. GraphRNN originally tackles undirected graph structure generation You et al. (2018), and we adopt an extension of it for attributed DAG generation Zhhng et al. (2019). D-VAE is a vari- ational auto-encoder and employs a nodewise autoregressive decoder. Both GraphRNN and D-VAE employ topological orderings and one-hot encoding of node IDs Zhang et al. 2019 GraphPNAS sequentially generates incident edges for node set of constant size, using mixture of Bernoulli dis-
tributions to model intra-set dependencies. To compare the capability of LAyerDAG in set generation against GraphPNAS, we further adapt GraphPNAS by using mixtures of multinoulli distributions for generating set of node attributes and setting the node set size be the averaged layer size. For
7

---

Published as a conference paper at ICLR 2025
Table 1: Evaluation results on LP. Best results are in bold.
Model
Validity
W, MMMD
Validity
W, /MM
Validity
Wi /MMD
M(x100))
[100]]
[V00]]
D-VAB
0.27 1: 0.03
8.7 4: 1.0
0.3
0.37 1 0.01
9.8 1: 1.6
1..00.6
0.59 0.00
8.5 0.0
1.9
GraphRNN
0:25 0.02
0.2::02
1221..2
0.31 1 0.07
12.01 0.00
18200.2
0.59 1 0.02
14.0.111.
2.100.1
GraphPNAS
4..0=4.0
2.2.+0.77
20.0 0:000:30
3.+1:3
0.67
4.00++3.0
0.6
OneShotDAG
0.37
6.4
1.5+0..1
0.07
339 0.7
1.3++0.0
0.50
LayerDAG (T 1)
0.26 + 0.06
1.6 0.8
0.14
0.36 + 0.02
1.3 0.3
0.12=00.1
0.95 + 0.01
2.0+0..1
0.08 0.0
LayerDAG
0.56 4: 0.02
1.6 1.0
0.10 0.0
0.63 2.00 0.00
18
0.06
0.96 4: 0.02
1.
0.30
pure diffusion baselines, we implement OneShotDAG, non-autoregressive variant of LayerDAG. For the ablation study of multiple rounds of refinement, we report results with single denoising step, denoted by LayerDAG (T 1). For details of model extensions, see Appendix B
5.1 GENERATING SYNTHETIC DAGS WITH STRONG LOGICAL RULES (Q1)
To evaluate the model's capability in capturing logical rules by learning from valid DAGs, we pro- pose a synthetic dataset of latent preferential DAGs (LP). LP adheres various hard logical con- straints, including a constraint on the balanced level of binary node attributes among the node's predecessors. Specifically, we enforce that Um 122 I for any node v, where [.] is the (m) +2
floor function, and (2) is the number node v's predecessors with attribute i for E {0, 13. The parameter P 0.5, 1} helps assess how model performance varies under different degrees of constraint, where a lower value imposes stricter constraints (p = indicating |n (0) n (1) < 1)-
For full description of the dataset, see Appendix C
We use LP with different p's to generate the datasets Dp and train different generative models based on D,- After training, we use each model to generate DAGs of the same number as that in D,- To evaluate the hard logical constraints, we assess the validity of generated DAGs by measuring the proportion of generated DAGs that satisfy the imposed hard constraints. To evaluate the soft constraints, we compare the distributions of graph statistics between generated DAGs and an equal number of real DAGs. We measure the 1-Wasserstein distance (Wi) between the distributions of layer numbers (I.) for the two graph sets. Additionally, we measure Maximum Mean Discrepancy (MMD) You et al. (2018) between two sets of graph statistic distributions corresponding to the graph sets. Specifically, we report MMD for the distributions of layer size (V"").
Table D presents the evaluation results. LayerDAG consistently outperforms all the other models in terms of validity, with substantial margins observed under stricter logical rules (lower p val- ues), about 20% in absolute value. Nodewise autoregressive models (GraphRNN and D-VAF) that directly encode node IDs struggle to learn strict logical rules. Meanwhile, a mixture of Bernouli/multinolli distribution is also not expressive enough, resulting in GraphPNAS achiev- ing low validity scores. The ablation studies against the non-autoregrressvve variant (OneShotDAG) and the menlleddnoising-ster variant (T 1) underscore the importance of combining autoregres- sive layerwise generation and diffusion in modeling strong directional and logical rules for DAG generation. In terms of graph statistics, the layerwise autoregressive models, LayerDAG (7 1) and LayerDAG, yield better performance in capturing layerwise patterns (L and ()0)) demon- strating the benefit of autoregressive layerwise generation. We also experiment with a variant of the LP dataset that allows directly examining the validity of the generated node attributes, where LayerDAG also achieves the best performance consistently. See Appendix[D]es more details.
5.2 CONDITIONAL GENERATION FOR REAL-WORLD DATASETS FROM DIVERSE COMPUTATIONAL PLATFORMS (Q2)
Datasets. We repurpose three representative real-world datasets, originally developed for DAG property prediction, to serve as testbeds for conditional DAG generation. The datasets are associ- ated with computation workloads executed on diverse hardware platforms, and they well fit the end scenario of synthetic data sharing for system/hardwware benchmarking. Originally released as part of the TpuGraphs dataset, TPU Tile is collection of kernel graphs for machine learning workload
8

---

Published as a conference paper at ICLR 2025
Table 2: Dataset statistics. [V. [&), and L are averaged over graphs. [ is averaged over layers.
Dataset
# graaphs
max [V]
[6]
mux [8]
[
maxx [
#attributes
info
TPU Tile
6, 301
40.8
394
42.9
711
11.2
3.6
21
TPU runtime
HLS
2. 062
88.6
356
110.7
477
27.75
78
3.2
28
7
FPGG resource usage
NA-Edge
2. 000
231.1
339
265.8
1.5
mohile CPU inforence latency
Table 3: Evaluation results for conditional generation. Best results are in bold.
TPU Vile
Nodd
MMND
XL
W. HMMD
MAE
Poursn
MAE
Pounson 1:506 0.000
MAE 1.5:2/011
Real graphs
0.75
ULB Buo0
0.3: M1D
0/52 cmm
13:.00
1.:1-0.3
0.8
BTTH 1. 0/13
0.3
T1: 1.0
2.4 033
0.10
10:1-0.1
13:1-33
14: 1.0
QupteNAs
0:24:-0.10
21.03
6.200.3
10:88 8.5
(0662:000 8.05
23
20
$8:001
2 2.115
18:20:0
16:600
OocSa-dDMG
1s
0.000.
8.1
003
4.
244
47
I L.peetiA:
0.63 0.01
12201
13:40
0.1 00
0.65 0.02
1.1 6.2
11:50
14:00.0
01500 L 0.000
0.9 0.3
1.100
0:11101
on Tensor Processing Units (TPUs), with graph labels y indicating the runtime averaged over set of compilation configurations (Phothilimthana et al.) 2023b). High-level synthesis (HLS) is a col- lection of data flow intermediate representation graphs for compiled C programs, with each DAG labeled according to the resource usage of look up table measured on Field Programmable Gate Arrays (FPGAs) (Wu et al., 2022). NA-Edge is a collection of DAGs representing neural architec- tures, with labels indicating their inference latency on mobile CPU (Dong & Yang] 2020: ZZhang (tt al.] (022). Table presents the dataset statisties. We perform a random train/val/test split for all datasets. For more details on dataset adaptation and data statistic distributions, see Appendix F+]
Evaluation. Performing ground truth evaluations for conditional generation of DAGs in system and hardware design requires direct measurements on specific computational platforms. For example, the HLS dataset requires program implementation and measurement on FPGAs (Wu et al., 2022). Such evaluations are computationally costly or infeasible due to limited access. Additionally, they demand specialized domain knowledge that often exceeds the expertise of general machine learning practitioners. Recently, employing ML-based surrogate cost models has emerged
popular and
effective alternative to direct measurement in various system and hardware optimizations (Chen
et al. 2018; Jia et al. 2020 Phothilimthana et al., 2023b Kaufman et al.] [021] Mendis et al.]
Sykora et al. 2022 Steiner et al. 2021 Baghdadi et al.) 2021 Zheng et al. 2020 Dubach al. 2007). In light of these achievements, we propose evaluate the quality of generated DAGs with ML-based surrogate models. Specifically, we partition the real labeled DAG datasets into training/validationneess subsets. Then, we use the real training and validation labels conditions for DAG generation.. The generated labeled DAGs essentially form synthetic training and validation subsets. Inspired by previous practices (Yoon et al., 2023, Li et al., 2023b). we train two ML models with BiMPNN using the same automated pipeline respectively on the real and synthetic training/validatioon subsets. We then compare the performance of the two models on the real test set. A generative model is considered better if its corresponding model achieves a performance closer to that of the model trained on the real subsets.
2019
Table 3 presents the evaluation results. For comprehensive analysis, we report two metrics for ML-based evaluation - Pearson correlation coefficient that compares the relative label differences of DAGs in the test set based on the predicted labels and the ground-truth labels, and mean absolute error (MAE) that compares the absolute difference between the predicted labels and the ground-truth labels. LayerDAG consistently achieves the best performance in MI-bbasdd evaluation. Further- more, we assess discrepancies in graph statistics between the real validation subset and a synthetic validation subset via the same metrics used in See 5.1] where LayerDAG also achieves the best per- formance in general. Overall, these evaluation results are aligned with previous observations made for the LP dataset.
5.3 LABEL GENERALIZATION IN CONDITIONAL GENERATION (Q3)
To assess the model generalization to unseen regimes of label values, we establish a challenging dutto--distribution testbed using the TPU Tile dataset. We sort the real-world DAGs based on their labels and then partition them into five quantiles. For an experiment, we exclude one quantile of data during the development of the generative models. After training the generative models,

---

Published as a conference paper at ICLR 2025
Table 4: Evaluation results for label generalization. Best results are in bold.
jestopllatoon
Inaepiation
BMPPN
Kogy'
MMMD [S*](((0""))
BIMTINNN
Saygle
Wis MMN
Real srapha
1:3.2 GJB
10:1
18 BG
(:31 2.0
0.3 i LL1
-0.09 1111
1:311:1
1110
6.5 1.1
15.31.
13:00
Gua688NN
=
0.2:
5.4.1.
4.5 12
14
5.03
0.00
345 1.
087 +-0.1
177000
1.+000
0.11=0002
0:34
26 00
70
4-1 2.0.
0.08 2.00
00: 00
0.8 4:002
14200
74802
434.01
LayeDAG
+:001
0.2
1.
0.00
0.4
1.200
0.3:0:1111
Tile
HISS
1.0
1.0
1.0
0.9
Rabio mas valdity
Basio of mar Peatson
0.8
0.8
0.8
0.7
0.6
0.7-
lineat constant
0.6
Railo
0.5
constant
0.5
constant
D-VAE
GraphRMN GrophPNAS
GraphRMN
GraphRMNN
GrophPNAS
GraphPNAS
0.3
0.0
0.2
0.4
0.6
0.8
L.0
0.5
1.0
1.5
022
0.4
0.6
0.8
L.0
Ratio time
Ratio time
Ratio of
Figure 2: Generation quality with respect to time budget for LP (p= 0). TPU Tile, and HLS.
conduct random train/val/test split on the previously excluded quantile. We evaluate conditional generation exclusively this quantile, i.e., generating DAGs conditioning on labels from this quan- tile. Essentially, this setup requires the models to perform interpolation for intermediate quantiles and extrapolation for the end quantiles. An analysis of the TPU tile dataset reveals long-tailed label distribution, with larger value ranges latter quantiles, detailed in Appendix E Therefore, we choose the 5th quantile for extrapolation study and the 4th quantile for interpolation study, which presents significant challenges. Besides the previously employed BiMPNN model, we lever- age another surrogate model that stood out top-5 solution from more than 600 submissions in
Kaggle competition for the TpuGraphs dataset (Phothilimthana et al. 2023a Kag 2023
Table|4peesent the evaluation results. As expected, the extrapolation setting is particularly difficult, with most baselines failing to attain a single positive Pearson correlation. By contrast, LayerDAG consistently outperforms competitors, improving BiMPNN's correlation by up to 0.2. While 0.2 remains modest for practical usage, the combination of autoregressive layerwise generation and diffusion drives LayerDAG stronger generalization across both settings.
5.4 EVALUATION FOR THE LAYER-INDEX-BRT BASEED DENOISING SCHEDULE (Q4)
Figure presents the evaluation of layer-index-baree based denoising schedule quality-efficiency trade- off on LP (p = 0). TPU Tile, and HLS. The curves start from the time budget that leads to the best performance. For an ablation study, we also experiment with a constant denoising schedule that simply utilizes constant number of denoising steps T for all layers. Both schedules allow an effective quality-efficinncy trade-off, while the layer-index- index-based schedule often yields a better generation quality with the same time budget. For comparison, time of the baselines using the same batch size. Using layer-index- linear denoising schedule, LayerDAG exhibits better comparable trade-off than most baselines except GraphRNN.
also evaluate the generation
CONCLUSION
We propose LayerDAG, a layerwise autoregressive diffusion model for DAGs, conceptualized by viewing DAG sequence of bipartite graphs. Extensive experiments synthetic and real- world datasets demonstrate a superior capability of LayerDAG in modeling the strong dependencies common in DAG data and in generating DAGS even with out-i--distribution labels.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
We are deeply grateful to Haoyu Wang and Yinan Huang for their insights on dataset adoption and adaptation. M. Li, V. Shitole, E. Chien and P. Li are partially supported by NSF awards PHY- 2117997, IIS-2239565, IIS-2428777, and CCF-2402816. 16; DOE award DE-FOA-0002785; JPMC faculty awards; Microsoft Azure Research Credits for Generative AI; and Meta research award.
REFERENCES
5th place solution of kaggle fast or slow competition. htttp:://giitub..com// Sooglle--ppp-graap-------------- 2023.
Andrew Adams, Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzu-Mao Li, Michaël Gharbi, Benoit Steiner, Steven Johnson, Kayvon Fatahalian, Frédo Durand, et al. Learning to optimize halide with tree search and random programs. ACM Transactions on Graphics (TOG), 38(4): 1-12, 2019.
Byung Hoon Ahn, Prannoy Pilligundla, Amir Yazdanbakhsh, and Hadi Esmaeilzadeh, Chameleon: Adaptive code optimization for expedited deep neural network compilation. arXiv preprint arXiv:2001.08743; 2020.
Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Tech- niques, and Tools (2nd Edition). Addison Wesley, 2006.
Sohyun An, Hayeon Lee, Jaehyeong Jo, Seanie Lee, and Sung Ju Hwang. Diffusionnag: Predictor- guided neural architecture generation with diffusion models. In International Conference Learning Reprexentations, 2023.
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, pp. 17981-17993, 2021.
Riyadh Baghdadi, Massinissa Merouani, Mohamed-Hichanl Leghettas, Kamel Abdous, Taha Ar- baoui, Karima Benatchba, al. A deep learning based cost model for automatic code optimiza- tion. Proceedings of Machine Learning and Systems, 3:181-193, 2021.
Jørgen Bang-Jensen and Gregory Gutin. Digraphs: theory, algorithms and applications. Springer Science & Business Media, 2008
Denis Borenstein. A directed acyclic graph representation of routing manufacturing flexibility. Eu- ropean journal of operational research, 127(1):78-95 2000.
Kaidi Cao, Mangpo Phothilimthana, Sami Abu-El- EljHai Dustin Zelle, Yanqi Zhou, Charith Mendis, Jure Leskovee, and Bryan Perozzi. Learning large graph property prediction via graph segment training. Advances in Neural Information Processing Systems, 36, 2023.
Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Learning to optimize tensor programs. Advances in Neural Informa- tion Processing Systems, 31, 2018.
Xiaohui Chen, Jiaxing He, Xu Han, and Li-Ping Liu. Efficient and degree-guided graph generation via discrete diffusion modeling. In Proceedings of the 40th International Conference on Machine Learning. pp. 4585-4618 2023.
Eli Cortez, Anand Bonde, Alexandre Muzio, Mark Russinovich, Marcus Fontoura, and Ricardo Bianchini. Resource central: Understanding and predicting workloads for improved resource management in large cloud platforms. In Proceedings of the 26th Symposium on Operating Sys- tems Principles, pp. 153-167, 2017.
Xuanyi Dong and Yi Yang. MAS-Bench-2001 Extending the scope of reproducible neural architec- ture search. In International Conference on Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2025
Zehao Dong, Weidong Cao, Muhan Zhang, Dacheng Tao, Yixin Chen, and Xuan Zhang. CkiGNN: Circuit graph neural network for electronic design automation. In International Conference on Learning Representations, 2023.
Christophe Dubach, John Cavazos, Bjöm Franke, Grigori Fursin, Michael FP O' O'Boyle, and Olivier Temam. Fast compiler optimisation evaluation using code-feature based performance prediction. In Proceedings of the 4th international conference on Computing frontiers, pp. 131-142, 2007.
Abhimanyu Dubey et al. The llama herd of models. arXiv preprint arXiv:2407.21783, 2024.
Yubo Gao, Maryam Haghifam, Christina Giannoula, Renbo Tu, Gennady Pekhimenko, and Nandita Vijaykumar. Proteus: Preserving model confidentiality during graph optimizations. In Proceed- ings of Machine Learning and Systems, 2024.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion prohabilistic models. In Advances in Neural Information Processing Systems, 2020.
Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. In International Conference on Learning Rep- resentations, 2021a.
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. In Advances in Neural Information Processing Systems. pp. 12454-12465, 2021b.
Chenqing Hua, Sitao Luan, Minkai Xu, Zhitao Ying, Jie Fu, Stefano Ermon, and Doina Precup. Mudiff: Unified diffusion for complete molecule generation. In Proceedings of the Second Learn- ing on Gruphs Conference, pp. 33:1-33:26, 2024.
Zhihao Jia, Sina Lin, Mingyu Gao, Matei Zaharia, and Alex Aiken. Improving the accuracy, scala- bility, and performance of graph neural networks with roc. Proceedings of Machine Learning and Systems, 2:187-198 1987-1997770 2020.
Jaehyeong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In Proceedings of the 39th International Conference on Machine Learning, pp. 10362-10383, 2022.
A. B. Kahn. Topological sorting of large networks. Commun. ACM, 5(11):558-562, 1962.
Sam Kaufman, Phitchaya Phothilimthana, Yanqi Zhou, Charith Mendis, Sudip Roy, Amit Sabne, and Mike Burrows. A learned performance model for tensor processing units. Proceedings of Machine Learning and Systems, 3:387-400, 2021.
Lingkai Kong, Jiaming Cui, Haotian Sun, Yuchen Zhuang, B. Aditya Prakash, and Chao Zhang. Autoregressive diffusion model for graph generation. In Proceedings of the 40th International Conference on Machine Learning, pp. 17391-17408, 2023.
Menghao Li, Minjia Zhang, Chi Wang, and Mingqin Li. Adatune: Adaptive tensor program com- pilation made efficient. Advances in Neural Information Processing Systems, 33: 13:14997-44819, 2020.
Muchen Li, Jeffrey Yunfan Liu, Leonid Sigal, and Renjie Liao. GraphPNAS: Learning probabilistic graph generators for neural architecture search. Transactions on Machine Learning Research, 2023a.
Mufei Li, Eleonora Kreačić, Vamsi K. Potluru, and Pan Li. Graphmaker: Can diffusion models generate large attributed graphs? arXiv preprint arXiv:2310.1383. 2023b.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint (tt1::88000033444 2018.
Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems, 2019.
12

---

Published as a conference paper at ICLR 2025
Zinan Lin, Alankar Jain, Chen Wang, Giulia Fanti, and Vyas Sekar. Using gans for sharing net- worked time series data: Challenges, initial promise, and open questions. In Proceedings of the ACM Internet Measurement Conference, pp. 464-483, 2020.
Shutian Luo, Huanle Xu, Chengzhi Lu, Kejiang Ye, Guoyao Xu, Liping Zhang, Yu Ding, Jian He, and Chengzhong Xu. Characterizing microservice dependency and performance: Alibaba trace analysis. In Proceedings of the ACM Symposium on Cloud Computing, pp. 412-426, 2021.
Charith Mendis, Alex Renda, Saman Amarasinghe, and Michael Carbin. Ithemal: Accurate portable and fast basic block throughput estimation using deep neural networks. In International Confer- ence on machine learning, pp. 4505-4515. PMLR, 2019.
Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In Proceedings of the 38th International Conference on Machine Learning, pp. 8162-811 -17121171,,- 2021.
Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Per- mutation invariant graph generation via score-based generative modeling. In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, pp. 4474 4484, 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vetoto, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, pp. 8024-8035, 2019.
Tim Pearce, Tabish Rashid, Anssi Kanervisto, Dave Bignell, Mingfei Sun, Raluca Georgescu, Ser- gio Valcarcel Macua, Shan Zheng Tan, Ida Momennejad, Katja Hofmann, al. Imitating human behaviour with diffusion models. In The Eleventh International Conference on Learning Repre- sentations, 2023.
Judea Pearl. Causal diagrams for empirical research. Biometrika, 82(4):669 688, 1995.
William Peebles and Saining Xie. Scalable diffuusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pp. 4195-4205, 2023.
Mangpo Phothilimthana, Sami Abu-El-Haija, Bryan Perozzi, Walter Reade, and Ashley Chow. Google fast slow? predict Al model runtime. https: hoss://www /wwp//wwww//// kaggle.
com/ wttpp//eiiiinnsrrrrrcdaaaeaaaaaa
ime) 2023a. URL htttps://ww.
kaggle cww http:///w..ooooeeeeooooo//eeeaaa
Phitchaya Mangpo Phothilimthana, Sami Abu-El-Haija, Kaidi Cao. Bahare Fatemi, Michael Bur- rows, Charith Mendis, and Bryan Perozzi. TpuGraphs: A performance prediction dataset on large tensor computational graphs. Advances in Neural Information Processing Systems, 2023b.
Kashif Rasul, Calvin Seward, Ingmar Schuster, and Roland Vollgraf. Autoregressive denoising dif- fusion models for multivariate probabilistic time series forecasting. In International Conference on Machine Learning, pp. 8857-8868. PMLR, 2021.
Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High- resolution image synthesis with latent diffusion models. Proceedings of the IEEE/VV Con- ference on Computer Vision and Pattern Recognition (CVPR), pp. 10684-10695, 2022.
Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1715-1725, 2016.
Steven S. Skiena. The Algorithm Design Manual. Springer, 2008
Srinivas Sridharan, Taekyung Heo, Louis Feng, Zhaodong Wang, Matt Bergeron, Wenyin Fu, Sheng- bao Zheng, Brian Coutinho, Saeed Rashidi, Changhai Man, and Tushar Krishna. Chakra: Ad- vancing performance benchmarking and co-design using standardized execution traces. arXiv preprint arXiv:2305.1455 2023.
13

---

Published as a conference paper at ICLR 2025
Benoit Steiner, Chris Cummins, Horace He, and Hugh Leather. Value learning for throughput opti- mization of deep learning workloads. Proceedings of Machine Learning and Systems, 5:323-334, 2021.
Ondiej Sýkora, Phitchaya Mangpo Phothilimthana, Charith Mendis, and Amir Yazdanbakhsh. Gran- ite: A graph neural network model for basic block throughput estimation. In 2022 IEEE Interna- fional Symposium on Workload Characterization (IIWC)) pp. 14-26. IEEE, 2022.
Kazuyoshi Takagi. Design and analysis of visi circuits based on directed acyclic graphs. 1999.
Robert Tarjan. Depth-first first search and linear graph algorithms. SIAM Journal Computing, 1(2): 146-160, 1972.
Peter W G Tennant, Eleanor Murray, Kellyn F Amold, Laurie Berrie, Matthew P Fox. Sarah C Gadd, Wendy J Harrison, Claire Keeble, Lynsie R Ranker, Johannes Textor, Georgia D Tomova, Mark Gilthorpe, and George T H Ellison. Use of directed acyclic graphs (DAGs) to identify confounders in applied health research: review and recommendations. International Journal of Epidemiology, 50(2):620-632 2020.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Infor- mation Processing Systems, 2017.
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In International Conference on Learning Representations, 2023a.
Clément Vignac, Nagham Osman, Laura Toni, and Pascal Frossard. Midi: Mixed graph and 3d denoising diffusion for molecule generation. In Machine Learning and Knowledge Discovery in Databases: Research Track, pp. 560-576, 2023b.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li. and Zheng Zhang. Deep graph library: A graph-centric, highly-performant package for graph neural networks. arXiv preprint (rXiv:1909.0/3/1 2019.
Zhendong Wang, Jonathan Hunt, and Mingyuan Zhou. Diffusion policies as an expressive policy class for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023.
Wei Wen, Hanxiao Liu, Yiran Chen, Hai Li, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. In European Conference on Computer Vision, pp. 660- 676, 2020.
Nan Wu, Hang Yang, Yuan Xie, Pan Li, and Cong Hao. High-level synthesis performance prediction using gnns: benchmarking, modeling, and advancing. In Proceedings of the 59th ACM/IEED Design Automation Conference, DAC '22, pp. 49-54, 2022.
Minji Yoon, Yue Wu, John Palowitch, Bryan Perozzi, and Russ Salakhutdinov. Graph generative model for benchmarking graph neural networks. In Proceedings of the 40th International Con- ference on Machine Learning, pp. 40175-40198, 2023.
Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovee. GraphRNN: Generat- ing realistic graphs with deep ruto-regressive models. In Proceedings of the 35th International Conference on Machine Learning, pp. 5708-5717, 2018.
Li Lyna Zhang, Shihao Han, Jianyu Wei, Ningxin Zheng, Ting Cao, Yuqing Yang, and Yunxin Liu. nn-meter: Towards accurate latency prediction of deep-learning model inference diverse edge devices. In Proceedings of the 19th Annual International Conference on Mobile Systems, Applications, and Services, pp. 81-93, 2021.
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-VAE: A variational autoencoder for directed acyclic graphs. In Advances in Neural Information Processing Systems, 2019.
14

---

Published as a conference paper at ICLR 2025
Lianmin Zheng. Chengfan Jia, Minmin Sun, Zhao Wu, Cody Hao Yu, Ameer Haj-Ali, Yida Wang, Jun Yang, Danyang Zhuo, Koushik Sen, et al. Ansor: Generating {High- Brigh-Performnce) tensor programs for deep learning. In 14th USENIX symposium on operating systems design and imple- mentation (OSDI 20), pp. (63-879,00 2020.
Kaijie Zhu, Jiaao Chen, Jindong Wang, Neil Zhenqiang Gong, Diyi Yang, and Xing Xie. Dyval: Graph-informed dynamic evaluation of large language models. In International Conference on Learning Reprexentations, 2024.
A DETAILS ON LAYERWISE DIFFUSION
Composing the transition matrices across multiple time steps yields the closed-form expression (Z((+1))2 O (++1) where Q (t-1) = -.. (..QQ.()) which allows parallel train-
ing across samples and time steps. An instantiation {Q He is valid as long as lim Q is known prior distribution. During the reverse generation process, the trained denoising network is used to convert (TT) drawn from the prior distribution into realistic data. Iteratively, compute
t) Z (Q(()) @ 2 (("0(t where T denotes transpose, and denotes element-wise product.
and sample from
Following the practice of DiGress, we use the empirical marginal distribution of a categorical at- tribute m RC as its corresponding prior distribution, which was observed to yield more efficient generation compared with uniform prior in practice. The composed transition matrix is chosen
to be Q = ( + (1 (1-00 (+)) 1m where (1 = cos?
the cosine noise sched- ule (Nichol & Dhariwal 2021). I E CxC is the identity matrix, and 1 E RC is the one-valued vector. As f -> T, the probability for real categorical attributes to be corrupted into random samples from the prior distribution approaches 1.
т t/T+s 2 1+s
In addition, we propose two modifications the diffusion process that better preserve the layerwise patterns of DAGs. To handle the potential uneven graph sparsity with respect to layer depth I, we
set the prior probability of a directed edge (u, v) for u E v(s) and v E D(+1) to be min (in)()())) .do... [VE
where d is the average node in-degree the training data. As all nodes in V p()) have at least one predecessor, we enforce this property in the sampling for graph structure corrpption and generation.
To generate ((-1), the node attribute prediction module first samples x(+1,Txx) E B Uxc from its prior distribution, where Tx is the maximum number of denoising steps. Then it- eratively, it samples ((+1,1) with denoising network Φbx (G(S)), x(1+,,++), [ 1) for = Tx 1,7x 2,... ... Similarly, the edge prediction module iteratively samples A (1+1,1) with denoising network des (G(5),X(11 ((+1), A (141,41), 1).
B BASELINE EXTENSIONS
General extension for DAG generation. To extend generative models of undirected graphs for DAG generation, we constrain the structure generation to the lower-triangular part of adjacency matrices with topological ordering.
GraphRNN. GraphRNN originally employs rows of an adjacency matrix for both the encoder input and decoder output. Following the practice of (Zhang et al. 2019), we augment them with one-hot encodings of categorical attributes for encoding and predicting the node attributes.
GraphPNAS. We use two separate encoders for node attribute prediction and structure prediction as in LayerDAG. Repeatedly, the model first predicts the categorical attributes of a new set of nodes given the partially generated DAG, and then it predicts the incident edges of the new nodes given the partial DAG and the new node attributes. We model the termination of DAG generation as an extra node attribute, which enables the model to generate DAGs with arbitrary number of nodes different from multiples of the pre-specified size.
We extend the official implementation for D-VAE and GRAN, both use MIT license.
15

---

Published as a conference paper at ICLR 2025
TPU Tile
HLS
NA-Edge
0.4
0.25
0.5
0.3
Proportion
Proportion
Proportion
0.4
0.15
0.2
0.3
0.10
0.1
0.05
0.00
0.0
0.0
20
20
Layer size
Layer size
Layer size
Figure 3: Layer size distribution in the real world datasets.
TPU Tile
HLS
NA-Edge
12
10
25
Labell value
20
20
Label
1.5
10
0
2000
4000
6000
500
1000
1500
2000
500
1000
1500
2000
sample
sample
sample
Figure 4: Scatter plot of the sorted labels. The label distributions in the real-world datasets are long- tailed.
C A SYNTHETIC DATASET OF LATENT PREFERENTIAL DAGs (LP)
A latent preferential DAG is constructed as follows.
1. Randomly sample the number of layers L ~ u {2,5).
2. Create the first layer of [D(1]] u 5) nodes. Each node is associated with random binary attribute or 1.
3. For 2,......
(a) Create layer of [200 ~ ~ (1,5) nodes. Each node is associated with random binary attribute 0 or 1.
(b) For each new node v:
i. An edge (u, v) is created with probability -.-d., where d, [ is the depth of node and d, > du.
(6) ii Let no be the number of predecessors of node v with attribute for e 1).1).
We enforce that [[n!")- (n
< p. where [.] the floor function.
(n. +n. 1/2
(1) 21 (1,4)
iii n2 = + n2
The logical rules for predecessors get increasingly relaxed goes from 0 to 1.
D VARIANT OF THE LP DATASET FOR ASSESSING THE VALIDITY OF GENERATED NODE ATTRIBUTES
We extend the original synthetic dataset with p 0 (full balance requirement). Specifically,
Each node now has three binary attributes (previously one).
16

---

Published as a conference paper at ICLR 2025
Table 5: Evaluation results the extended synthetic dataset for p 0 (full balance requirement). Best results are in bold.
Model
Validity
Wi MMM +
balance
attribute
full
L
|
attribute
D-VAE
0.536
0.057
0.039
5.1e
1.6e
2.5e
GraphRNN
0.547
0.172
0.094
5.8e-1
1.2e
8,5e-
LayerDAG
0.578
0.274
0.195
1.8e-1
2.5e
7.8e
For nodes in the first layer, all three binary attributes are randomly sampled from prior Bernoulli distributions.
The first attribute is still used for determining edge connections based on balance.
The second and third attributes of an intermediary node are assigned the most and least common corresponding attribute values among its predecessors, respectively. This design is inspired by real-word world scenarios, such tensor dimension matching in computational graphs. In cases of ties, attribute values are assigned randomly.
In addition to the previously adopted metrics, we also report balance-only validity and feature-only validity as key components of the full validity metric, as well as MMD for feature distributions. Table compares LayerDAG with the two most competitive baselines concluded from the other experiments, with results averaged over three random seeds. Overall, LayerDAGG achieves the best performance across all metrics. This demonstrates LayerDAG's superior capability in generating valid attributes and learning the attribute distribution.
E ADDITIONAL DETAILS ON FEAL-WORLD DATASETS AND ADAPTATION OF THEM
TPU Tile. In the original dataset, each data sample includes computational graph, compilation configuration, and the execution time of the graph on TPU when compiled with that configuration. A single graph may appear in multiple data samples and have multiple associated compilation con- figurations. We simplify the dataset by averaging the runtime across all compilation configurations for each graph. As the labels of the test set were not released, we re-perform split of the labeled samples.
HLS. We randomly choose 20% of the original graphs.
For all three real-world datasets, we perform a 80/10/10 random split of the dataset. All three datasets exhibit long-tailed layer size distributions (Fig. 3 and label distributions (Fig.
TPU Tile was originally part the TpuGraphs dataset, which uses Apache-2.0 license. The HLS dataset is not released with license. NA-Edge is released with MIT license part of the nn- Meter project.
F EXPERIMENT DETAILS
F.1 MODEL DEVELOPMENT
For the synthetic LP dataset, we tune the hyperparameters based on validity. For conditional gener- ation, we tune the hyperparameters based on Pearson correlation coefficient. For each experiment, an early stop is performed based on validation accuracies (for layer size prediction) negative log likelihoods (for diffusion).
F.2 ML-BASED EVALUATION
We perform ML-based evaluation by implementing standardized AutoML pipeline. Based empirical studies, the best BiMPNN model selected based on validation Pearson correlation coef- ficient, and the best Kaggle model is selected based on validation mean absolute emor.
17

---

Published as a conference paper at ICLR 2025
F.3 EXPERIMENTS COMPUTE RESOURCES
We have access to an Azure virtual machine equipped with 2 NVIDIA A100 PCLe GPUs, each with 80 GB of memory, 48 non-mulithheaaee AMD EPYC Milan processor cores, and 440 GiB of system memory.
F.4 IMPLEMENTATION
Our implementation based on PyTorch 1.12.0 (Paszke et al. 2019) and DGL 1.1.0 (Wang et al.
2019)
18


Reviews:
[{"review_id": "rtKP9H1Cw5", "reviewer": "Reviewer_MRjN", "summary": "This paper presents an autoregressive model, LayerDAG, for generating directed acyclic graphs (DAGs). A key contribution of the paper is framing the problem as a layered graph, leveraging the fact that a topological ordering of a DAG naturally induces a layered structure, where each pair of consecutive layers forms a directed bipartite graph. Building on this layered representation, LayerDAG employs autoregressive generation to model directional dependencies between layers, while diffusion models capture logical dependencies within each bipartite graph. Experimental results demonstrate that LayerDAG outperforms several existing graph generative models.", "questions": "1.\tGiven that the topological ordering of a DAG is not unique, how does the layered representation remain consistent for a given DAG? Was any consideration given to the ordering of nodes within each layer?\n2.\tWhat is the rationale for seeking permutation invariance when generating DAGs?\n3.\tIs it possible to validate the generated DAGs for the TPU Tile datasets experimentally, without relying on a surrogate model?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tGenerating DAGs is more challenging than generating general graphs due to their inherent dependencies and constraints. The layered structure simplifies the generation process by breaking down the DAG into a sequence of directed bipartite graphs, making dependencies easier to handle.\n2.\tLayerDAG's combination of autoregressive and diffusion models makes it a more robust approach to handling these complexities.\n3.\tLayerDAG offers a scalable solution for generating large, structured DAGs.\n4.\tThe paper demonstrates the improved performance of LayerDAG over other methods through experiments with various synthetic DAGs.", "weaknesses": "1.\tThe authors state that \"LayerDAG is based on a novel perspective of DAGs: as illustrated in Fig. 1(b), the partial order of nodes dictated by the DAG structure can be decoupled as a sequence of tokens, each corresponding to a bipartite graph.\" However, this approach has been widely known for decades. For example, Tarjan’s topological ordering algorithm for a DAG uses a Depth-First Search (DFS) traversal to produce a linear ordering of vertices, ensuring that for every edge, the source vertex appears before the target vertex in the ordering. Surprisingly, the paper does not reference Tarjan’s method or other relevant work in this area.\nCitation: Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160. doi:10.1137/0201010\n2.\tThe directional and ordered dependencies within a DAG structure are essential, meaning that order should be preserved. Thus, the motivation for seeking permutation invariance in this context is unclear. Furthermore, Proposition 3.1 lacks clarity, and a formal proof would help understand the proposition.\n3.\tIn Section 5.2, the experiments explore several real-world DAGs. However, the presented results indicate whether the generated DAGs can substitute training DAGs, which seems insufficient. For instance, the generated graphs have different layer counts than the actual DAGs. A more pertinent question would be whether the generated DAGs are suitable for downstream tasks. Although validating hardware DAGs might be challenging, it should be feasible to assess the relevance of other types of DAGs for specific applications (e.g., with the TPU Tile dataset).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PAc3ZOJUhx", "reviewer": "Reviewer_7SrQ", "summary": "The paper makes a compelling contribution by proposing a novel framework for DAG generation that addresses key challenges in modeling both logical and directional dependencies. The combination of autoregressive generation and diffusion models offers strong expressiveness, and the extensive experiments validate its practical utility. However, addressing the computational complexity and providing more interpretability would strengthen the work. Expanding the comparison with simpler models and exploring alternative encoding methods would also improve the empirical analysis. Nonetheless, the novelty and relevance of LayerDAG justify its acceptance.", "questions": "NA", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Innovative Approach: The combination of autoregressive and diffusion models provides a novel framework for generating complex DAGs with strong dependencies.\n\nLayerwise Decomposition: The use of bipartite graphs for sequential layer generation improves scalability and reduces computational complexity.\n\nConditional Generation Capability: LayerDAG supports generating DAGs based on specific performance metrics, making it valuable for system benchmarking applications.", "weaknesses": "Computational Overhead: While the layerwise approach is efficient, the combination of autoregressive and diffusion methods can be computationally intensive for very large graphs.\n\nLimited Exploration of Alternative Encodings: The paper mainly focuses on sinusoidal encodings, without exploring other potential positional encodings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kWotprt3zC", "reviewer": "Reviewer_72KY", "summary": "The paper presents a diffusion model LayerDAG for directed acyclic graphs (DAGs) based on a novel representation of DAGs as a sequence of bipartite graphs, each bipartite graph divided across nodes in the next layer of the DAG versus nodes in all previous layers of the DAG. This representation allows for layer-wise conditional generation of the DAG, which allows the model to better-learn logical rules. The experiments show that LayerDAG exceeds in learning hard logical rules, learning soft rules, and in generalization.", "questions": "Pg 6, proof of Proposition 3.1: what is does it mean to be \"permutation equivariant\"? Is this meant to read \"...invariant\"?\n\nThere is not enough discussion about how exactly the denoising steps interact with the successive layer-wise generation. It is not clear to me how the number of denoising steps relates to the number of layers. It is also jarring to read in S2 that in general diffusion generation is conditioned on previous steps, whereas in LayerDAG it is conditioned on previous layers. For example, the \"__Implementation__\" paragraph in page 5 reads \"Let $\\textbf{X}^{l+1,t}$ be the node attributes sampled for the $(l+1)^{\\text{th}}$ layer at the step $t$ in the reverse node attribute diffusion process.\" Is step $t$ nested under layer $l+1$, i.e. all steps $1,\\ldots,T$ occur in each layer, or do steps stretch over all layers? Similarly, S3.4 should be better-explained.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper's contributions stem from a novel formulation of a DAG as a sequence of layers. This formulation is original, non-trivial, and concise, and directly motivates the LayerDAG algorithm. The paper itself is quite clear and well-written. The experiments are comprehensive and clearly demonstrate the superior performance of LayerDAG over other autoregressive DAG models.", "weaknesses": "A minor weakness in the paper is that there is not enough discussion about the definition of LayerDAG across layers versus the usual definition of diffusion models across denoising steps. I elaborate more in the \"Questions\" section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QuZVWb01M3", "reviewer": "Reviewer_vg1z", "summary": "This paper proposes an autoregressive diffusion model to generate directed acyclic graph (DAG). This work observes that the DAG structure can be decoupled by a sequence of tokens, where each token corresponds to a bipartite graph. It is capable of generating larger DAGs (up to ~400 nodes). To validate the model, the paper compares the validity and statistical properties of the synthetic DAGs generated by the model with the baselines: computational graphs on TPU, flow graphs in FPGA, and Neural architectures on edge devices. They use the synthetic DAGs to train a ML-based surrogate model to measure the performance of systems (inference time, resource usage, etc.). And results show that the trained surrogate model outperformed ones that are trained on the baseline generative model.", "questions": "Questions\n* What is the maximum number of layers of DAG your model could generate?\n* Is LayerDAG able to capture more complex logical constraints other than the number of predecessors? \n* Do you have explanations for the better performance of baseline models in Table 3, specifically HLS dataset?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Make a novel observation that DAG can be viewed as a sequence of bipartite graphs, which preserve the partial ordering and are autoregressive-friendly.\n* Explore and discuss different design choices for DAG generative models, including separating three modules, positional encoding, etc.\n* LayerDAG is permutation invariant, achieving good generalization.\n* Different experiments to evaluate the proposed model quality on different tasks", "weaknesses": "* In the beginning of the introduction (line 51), the author mentioned that the one of the challenge in DAG is the training LLM workload execution DAG involves trillions of operations. But this work is capable of generating nodes up to 400 nodes, which seems not to be able to solve the challenge mentioned above.\n* In the beginning of the introduction (line 51), the author mentioned that one of the challenges in DAG is the training LLM workload execution DAG involves trillions of operations. But this work is capable of generating nodes up to 400 nodes, which seems not to be able to solve the challenge mentioned above. Or do the authors suggest that using DAG with 400 nodes could capture the characteristics of a trillion of nodes? How do you get the logical constraints from the real-world large DAG for the synthetic DAG generation?\n* In D-VAE, they have additional experiments to evaluate the model quality, like reconstruction accuracy. Would like to see the comparison on those experiments.\n\nMinor issue\n* The symbol for DAG are not consistent (line 143 vs. line 207)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SuRJYsCP21", "reviewer": "Reviewer_qSxe", "summary": "This submission proposes a generative model, based on autoregression and dffusion, for Direct Acyclic Graph generation (DAG). The problem under study is relevant for the general scientific community with broad applicability in many crucial systems. \n\nThe main idea behind the method presented is to transform the topological order induced by the DAG into a series of bipartite graphs that capture sequential dependencies of the tasks represented within the DAG. This idea enables the authors to sequentially generate sets of nodes as if they were a layer of the DAG, overcoming issues with partial ordering of nodes within the topological order of the graph. This is where the autoregressive component of the algorithm comes in, as the generation of a new set of nodes is dependent on the previous layers generated by the model.\n\nThe authors propose evaluation on a new synthetic dataset capable of capturing logical dependencies between nodes of different layers with multiple levels of hard logical constraints. This evaluation method attempts to capture the generative model's ability to impose logical dependencies between nodes. The proposed model is further evaluated on the ability to generate DAGs that mimick the properties of DAG property prediction benchmark (supported by an ML-surrogate approach, following related work in the area) and generalization of generated label values. The proposed model shows better performance than related work using the chosen evaluation metrics.", "questions": "Overall I do not have many questions as I believe this is a high quality submission, however:\n\n- As mentioned in the weaknesses section, I think the paper would be improved by a critical analysis of the experimental results. I understand that space limitations can prevent this, but a high quality discussion of results is more valuable than quantity of benchmarks. For example, how significant is a difference in Pearson correlation of **at most** 0.2 in the generalization benchmark? Is the model able to generalize at all, even if the coefficient is slightly higher than the baselines?\n\n- What is the impact of a BiMPNN instead of considering message passing solely along the direction of the edges?\n\n- If the complexity of generation increases per layer, have you considered using an exponential denoising schedule?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The method is simple, easy to understand and solidly rooted on a wealth of methodology on autoregressive diffusion models.\n- The simplicity of the method does not detract the ingenuity of transforming the topological partial ordering into a sequence of bipartite graphs, leveraging that for generation.\n- The authors are not over-reliant on mathematical formulation to describe their method (often a problem with diffusion based contributions), striking a balance between textual/intuitive explanations with easy to follow maths.\n- Contribution of a synthetic dataset is extremely positive, as it helps testing for a wide range of possibilities that are often not considered with benchmarking datasets (that, in turn, are often not predictive of performance in real-world problems).", "weaknesses": "- Although the authors claim a significant increase in the number of nodes generated per DAG (from 24 to 400), this is still far from truly complex DAGs that can number in the thousands.\n\n- There is a lack of critical analysis on the experimental results and the variations in performance of the proposed method. For example, the difference in LayerDAG with a single denoising step to the full algorithm for some benchmarks are negligible, it would be good to have some insight on why and in which conditions is it worth performing multiple denoising steps (and the impact in training time).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)