acceptodds
Under review as a conference paper at ICLR 2027

DAG scheduling based on diffusion model with partial-order feasibility guarantee

Abstract

A central question for learning-based non-autoregressive directed acyclic graph (DAG) scheduling is how to represent and learn the solutions' global ordering structure, while guaranteeing that the solutions satisfy the partial-order constraints in the DAG. Existing approaches commonly predict the distribution of itemwise priorities, leaving the solution structure and partial-order feasibility to a post-processing feasibility repair procedure. In this paper, we propose a DAG scheduling framework based on a diffusion model in the doubly stochastic matrix (DSM) space with partial-order feasibility guarantee. The DSMs directly provide a continuous representation of scheduling solutions. We promote and ensure the feasibility of the DAG scheduling solutions generated by our framework from both the perspective of training and inference. At inference, we propose a feasible solution decoding procedure for DAG scheduling that can directly produce feasible solutions without additional post-processing repair, which applies our Birkhoff-von Neumann (BvN)-based feasible solution extraction algorithm to the diffusion model's DSM output. The efficiency of the decoding is supported by a successor interpretation of permutation matrices. At training, we further design a learning method guided by feasible components, to promote the DAG scheduling solutions' feasibility and quality. Comparison experiments and ablation studies evaluate the solution optimization performance of our framework across different DAG scheduling tasks.

Primary area:
optimization
Keywords:
DAG scheduling, partial-order constraints, diffusion model, doubly stochastic matrix

Reviews

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

The paper proposes a diffusion-based framework for DAG scheduling using doubly stochastic matrices as continuous solution representations. It introduces a successor interpretation of permutation matrices, a Birkhoff–von Neumann-based feasible solution extraction procedure, and feasible-component guidance during training.

Critical strengths
  1. The paper provides a structured approach to generating feasible DAG schedules and explicitly addresses partial-order constraints during decoding.
  2. Experiments cover multiple problem families and scales, with ablations evaluating feasible decoding and feasible-component guidance separately.
Critical weaknesses
  1. The reported relative gaps for TPC-H and Pegasus are measured against heuristic or metaheuristic reference solutions rather than certified optima. They therefore do not directly establish optimality gaps.
  2. The decoding procedure thresholds small residual entries and may terminate an extraction attempt when no supported successor is available. The practical frequency and handling of such cases are not sufficiently clear.
Questions for authors

See the above. Also, after residual thresholding, does the decoder always produce at least one complete feasible ordering? Please clarify how cases in which extraction terminates prematurely are handled.

1 comment

Thank you for your valuable feedback. Our response are as follows.

1. The reported relative gaps for TPC-H and Pegasus are measured against heuristic or metaheuristic reference solutions rather than certified optima. They therefore do not directly establish optimality gaps.

his gap refers to the gap relative to the reference solution instead of the certified optimum. To avoid confusion, we have changed the word "gap" to the "drop" compared with the reference solution, following the previous work (such as Fast-T2T) that incorporate heuristic reference solutions.

2. Would small residual entries terminate an extraction attempt when no supported successor is available?

During the experiments, we find that the decoder still always produces feasible orderings after introducing the threshold. Because the condition for generating a DSM SθS_\theta that is not feasibly decomposable is still very strict: firstly, the range of z0^\hat{z_0} should large, leading to an entry to be less than the threshold in DSM SθS_\theta; secondly, this entry happens to fall within the only topological sorting of the DAG.

However, it can be suggested to reduce the threshold when the DAG size n is large, and impose a regularization term on z0^\hat{z_0} to limit its range. If a feasible solution still cannot be generated, an additional round of inference can be conducted beyond the top-K reasoning.

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

This paper proposes a diffusion-based framework for DAG scheduling using DSMs. It introduces a BvN-based feasible solution extraction mechanism and feasibility-guided training to satisfy partial-order constraints. Experiments on multiple DAG scheduling benchmarks demonstrate competitive performance.

Critical strengths
  1. The combination of DSM representations and feasibility-aware extraction provides an interesting approach to DAG scheduling.
  2. Experiment covers multiple benchmarks and problem scales.
  3. The paper is well structured.
Critical weaknesses
  1. Insufficient motivation. The advantages of DSM representations and the proposed extraction mechanism over conventional feasibility-preserving methods are not clearly justified. The motivation for reference-solution-based learning also remains unclear.

  2. Limited efficiency analysis. The paper lacks a systematic comparison of the computational benefits and overhead of feasibility-guided training against conventional post-processing approaches.

  3. Insufficient justification of the proposed design choices. While the paper provides motivations for DSM representations and feasibility-guided learning, it remains unclear whether the proposed framework offers sufficient advantages over simpler feasibility-preserving approaches. In particular, the necessity of diffusion, the benefits of BvN-based extraction over direct topological decoding, and the rationale for reference-solution-based supervision require further justification.

  4. Insufficient technical clarity. The scope of the feasibility guarantees, including potential extraction failures, requires clarification. Figure 1 also does not clearly distinguish the training and inference workflows.

Questions for authors
  1. The motivation remains insufficiently justified: what advantages do the DSM representation and the proposed extraction mechanism offer over conventional post-processing and constructive methods that also guarantee feasibility? Although the paper discusses challenges requiring new decoding and training procedures, the rationale for adopting reference-solution-based learning remains unclear.
  2. How can the benefits and computational costs of feasibility-guided training be fairly compared with those of handling feasibility through post-processing?
  3. Given existing combinatorial optimization methods that combine diffusion models with graph neural networks, please clarify the methodological novelty and scope of the proposed framework relative to these approaches.
  4. Please clarify the feasibility guarantees for the training and inference outputs, including whether additional repair is ever required and, if so, how frequently.
  5. Figure 1 does not clearly distinguish the training and inference data flows; please clarify the relationships among reference labels, constraint inputs, noise initialization, and stop-gradient operations.
  6. Is reporting N/A for feasibility appropriate? It may be misleading, as N/A does not necessarily indicate 100% feasibility. Please clarify what N/A means in the feasibility results.
2 comments
AuthorsOpenReview ↗

Response to Reviewer iqkR (1/2)

Thank you for your valuable feedback. Our response are as follows.

The efficiency analysis about the overhead of feasibility-guided learning:

We appreciate the reviewer’s suggestion to make more efficiency analysis to assess the benefits and overhead. We make a comparison of training time in the following Table A. The results show that the training time did not increase significantly when introducing feasibility-guided training , while the results in Table 1, 2 and 3 shows that our method achieves better scheduling performance.

Table A. Training overhead comparison.

TPC-H 10TPC-H 20TPC-H 30TPC-H 50TPC-H 100TPC-H 150
Positional Heatmap< 1 h< 1 h1 h4 h10 h25 h
Successor Heatmap< 1 h< 1 h1 h4 h11 h25 h
Ebrahimi et al.< 1 h< 1 h1 h1 h2 h2 h
Ours5 h6 h7 h10 h18 h40 h
Ours w/o FCG5 h6 h6 h8 h15 h29 h

The motivation and justification of the proposed design choices:

1. The necessity of diffusion. Firstly, diffusion-based framework provides a non-autoregressive inference for DAG scheduling with few-step denoising. Combining diffusion with DSM representation enables DAG scheduling to be directly supervised and optimized in the continuous domain. Secondly, diffusion model can learn diverse distribution via iterative refinements, which alleviates the expressiveness limitation of previous non-autoregressive methods.

2. The benefit of DSM representations and the proposed BvN-based extraction mechanism over conventional feasibility-preserving methods. The DSM representations provides a continuous representation for both the scheduling solutions and partial order constraints, and the proposed BvN-based extraction mechanism guarantees the solution feasibility and the consistency between the extracted solutions and the network output during inference, and provides a direction for learning feasible DAG scheduling solutions. Specifically, according to the BvN theorem, any DSM is a convex combination of multiple permutation matrices, which can function as a continuous representation of orderings. This motivates to use the DSM representation as the continuous representation of the partial order constraints, where the convex combination of successor permutation matrices satisfy the partial order feasibility is a DSM, i.e., $ \mathcal{P}_{C}^{\mathrm{pos}} := \operatorname{conv} \left\{ P_{\pi} : \pi \in \Pi_{C} \right\} \subseteq \mathcal{B}_{n} $. Based on the DSM representations, we further developed the BvN-based extraction, which ensures the feasibility. It also guarantees the consistency between the extracted solutions and the network output during inference, allowing to construct feasible components for training guidance, providing a direction for the learning of feasible DAG scheduling.

3. The rationale for reference-solution-based learning. The diffusion-based network models typically require supervised learning from reference labels. The feasible components guidance encourages feasibility but does not distinguish feasible schedules and high-quality feasible solutions. We therefore follow the common practice of existing diffusion-based combinatorial optimization methods, e.g., Fast-T2T, to use high-quality feasible reference solutions as supervision targets. Besides, to obtain high-quality feasible supervision signals for model training, we combined the results of heuristic algorithms and meta-heuristic algorithms. The comparison results shows that our method can achieve better performance against PPO-BiHyb and Qi et al. (2025) that are RL-based and do not incorporate supervision over reference solution.

Technical clarity about the feasibility guarantees and Figure 1.

1. The potential extraction failures. The BvN-based feasible solution extraction is guaranteed to produce at least one feasible solution. During the experiments, we find that the decoder still always produces feasible orderings. This is because that during the Sinkhorn normalization process of calculating SθS_\theta, z0^\hat{z_0} is regarded as logits before the row-wise and column-wise normalization operation, and the expexp operation is then executed first (as shown in Equation (14) in Appendix B.1). The resulting matrix will be always positive. Thus, the first iteration of the BvN-based feasible solution extraction will definitely decompose a feasible solution.

AuthorsOpenReview ↗

Response to Reviewer iqkR (2/2)

2. Clearly presenting Figure 1. We are grateful for the reviewer’s valuable suggestion to improve the demonstration of Figure 1. We have re-drawn Figure 1 by distinguishing and clarify the training and inference data flows. The frames of the process involving gradients during training are underlined in the manuscript.

The methodological novelty compared with existing combinatorial optimization methods that combine diffusion models with graph neural networks.

The existing diffusion-based methods for combinatorial optimization, such as Fast-T2T, can learn diverse distribution via iterative refinements, which alleviates the expressiveness limitation of previous non-autoregressive methods. They typically learn to denoise a heatmap of the independent binary variables of the problem solution, and then decode and repair a solution from the heatmap. But they are proposed for unconstrained or simply constrained problems, and cannot directly solve DAG scheduling which has complex constraints (partial order constraints). When applied to DAG scheduling, the heatmap of independent variables does not contain information about partial-order constraints, and the feasibility and the quality of the solution largely depend on the design of the decoding and repair process. Decoding and repairing from a heatmap also causes inconsistency between the network output and the solution, and make it difficult to further design a mechanism that guides the network output to satisfy the partial-order feasibility.

On the contrary, our designs can guarantee the feasibility of DAG scheduling during inference, maintain the consistency between the network output and the solution, and provide a direction for learning feasible DAG scheduling solutions. Specifically, the DSM space firstly provides a continuous representation for both the solutions and partial order constraints. Based on the DSM representations, we further developed the BvN-based extraction. The BvN-based extraction does not only ensure the feasibility, but also guarantees the consistency between the extracted solutions and the network output during inference. Its extracted solutions remain explicitly within the network output. Also, the BvN-based extraction also allows to construct feasible components for training guidance, providing a direction for the learning of feasible DAG scheduling.

In order to verify the advantages of our method, in the experiment, we have compared baselines positional heatmap and successor heatmap version of Fast-T2T, and Ebrahimi et al. (2026), which is a diffusion-based model. As presented in the experimental results in Table 1, 2 and 3, our method outperforms these methods in terms of scheduling objectives.

Is reporting N/A for feasibility appropriate?

N/A means that the corresponding method requires no additional feasibility repair. To avoid any confusion, in Table 1, 2 and 3, we have replaced the “feasible rate” from N/A to 100%, indicating that the corresponding method is guaranteed to produce feasible solutions.

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

This paper proposes a diffusion-based framework for DAG scheduling using doubly stochastic matrices to represent scheduling solutions. It introduces a BvN-based feasible decoding method and a feasible-component-guided training strategy to generate high-quality solutions while satisfying partial-order constraints.

Critical strengths
  1. The paper addresses an interesting and meaningful problem of generating high-quality DAG scheduling solutions while satisfying partial-order constraints.
  2. The paper presents a complete framework that integrates diffusion-based solution generation, feasibility-aware decoding, and feasibility-guided training, supported by extensive experiments and ablation studies.
Critical weaknesses
  1. The BvN-based feasible decoding essentially relies on a greedy topological construction. Since simpler constraint-aware decoding methods can also guarantee feasibility, the paper lacks a convincing comparison demonstrating the unique benefits of the proposed mechanism.
  2. The proposed framework involves diffusion sampling, Sinkhorn normalization, and iterative feasible solution extraction, introducing considerable computational overhead. However, the paper lacks comprehensive end-to-end runtime comparisons with existing learning-based methods and conventional optimization algorithms, making it difficult to assess its actual efficiency advantages.
  3. The training primarily relies on supervised learning from heuristic reference solutions and an additional feasible-component loss, without directly incorporating the scheduling cost. It remains unclear how effectively the proposed framework learns to generate high-quality optimization solutions beyond imitating existing heuristics.
Questions for authors
  1. For the test sets of the three benchmarks, what is the failure rate of the BvN-based feasible solution extraction during inference? Specifically, how many trajectories failed to yield a feasible solution, for instance, due to the support of the residual becoming empty?
  2. To support the claims regarding the efficiency of the non-autoregressive model, please provide the end-to-end inference times. including diffusion sampling and the generation of multiple trajectories via top-K, measured in the same hardware environment as the baselines.
1 comment

Thank you for your valuable feedback. Our response are as follows.

1. The comparison abount BvN-based feasible decoding (weakness 1):

In Table 1, 2 and 3, we have presented simpler constraint-aware decoding methods, especially the ablation study results of our method with simpler constraint-aware decoding methods (ours w/o FSD). The experimental results shows that our proposed method demonstrates advantages over the previous ones.

2. End-to-end runtime comparisons to access the computational overhead (weakness 2 and question 2):

We appreciate the reviewer’s suggestion to assess the timing efficiency of the framework. We have recoded the end-to-end runtime of each method in the following Table A, in addition to the wall-clock time of feasible solution decoding in Table 4, Appendix E in the previous manuscript. The results show that the inference time of our method is not inferior to that of the existing non-autoregressive method (Qi et al.), is much faster than the autoregressive method (PPO-BiHyb), while achieving better scheduling performance. Our method is also significantly faster than the GA-based metaheuristic method that is used to generate reference solutions. The ablation comparison between ours and ours w/o FSD also shows that the introduction of iterative feasible solution extraction did not significantly increase the inference time.

Table A. Average runtime required by each method to obtain a solution.

TPC-H 10TPC-H 20TPC-H 30TPC-H 50TPC-H 100TPC-H 150
Metaheuristic (GA)21s34s52s69s134s183s
PPO-BiHyb8.0s14.5s33s71s191s532s
Qi et al.203ms244ms302ms590ms801ms1630ms
Positional Heatmap18ms21ms23ms23ms37ms56ms
Successor Heatmap22ms23ms34ms41ms45ms47ms
Ebrahimi et al.10ms11ms10ms13ms15ms15ms
Ours40ms160ms295ms395ms1947ms1810ms
Ours w/o FSD46ms59ms93ms178ms599ms1.4s

3. Heuristic reference solutions (weakness 3):

The diffusion-based network models typically require supervised learning from reference labels. We therefore follow the common practice of existing diffusion-based combinatorial optimization methods (such as Fast-T2T) to use high-quality feasible reference solutions as supervision targets. Although supervised learning based on the reference solution is difficult to surpass the reference solution, it can still achieve competitive results. Besides, to obtain high-quality feasible supervision signals for model training, we have combined the results of heuristic algorithms and meta-heuristic algorithms.

The runtime reported in the above Table A shows that our method is significantly faster than the metaheuristic method (GA) that is used to generate reference solutions, demonstrating our advantage on efficiency. The comparison results in Table 1, 2 and 3 in the manuscript shows that our method can still achieve competitive results with the reference solutions. It also shows that our method can achieve better performance against the reinforcement learning methods that incorporate the scheduling cost (PPO-BiHyb and Qi et al.).

4. Failure rate of the BvN-based feasible solution extraction during inference (question 1):

During inference, the BvN-based feasible solution extraction is guaranteed to produce at least one feasible solution, so the failure rate is 0. Specifically, the input of the BvN-based feasible solution extraction in this paper, i.e., the DSM SθS_\theta, is a fully positive matrix, so the first iteration of the BvN-based feasible solution extraction will definitely produce a feasible solution. This is because that during the Sinkhorn normalization process of calculating SθS_\theta, z0^\hat{z_0} is regarded as logits before the row-wise and column-wise normalization operation, and the expexp operation is then executed first (as shown in Equation (14) in Appendix B.1). The resulting matrix will be always positive. To avoid any confusion, in Table 1, 2 and 3, we have replaced the “feasible rate” from N/A to 100%, indicating that the corresponding method is guaranteed to produce feasible solutions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.