- 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
- The paper provides a structured approach to generating feasible DAG schedules and explicitly addresses partial-order constraints during decoding.
- Experiments cover multiple problem families and scales, with ablations evaluating feasible decoding and feasible-component guidance separately.
Critical weaknesses
- 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.
- 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.
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θ that is not feasibly decomposable is still very strict: firstly, the range of z0^ should large, leading to an entry to be less than the threshold in DSM Sθ; 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^ 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.