Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper works on scheduling of a computational graph which is an NP-hard problem.
The paper considers a problem of scheduling a computational graph on a fixed no. of homogeneous devices.
The paper claims that the previous approaches take large number of evaluations for convergence and suggests proxies as a faster alternative.
Instead of trying to minimize the makespan measure w.r.t the proxy, this paper creates a set of candidates and learns a generative model to assign higher probability to the low-makespan schedules.
Overall, the paper is a case study of GFlowNets on scheduling computational graphs.
Main difference over GFlowNet baseline is (1) using a variance loss on the log-partition function, (2) learning a single model for multiple different reward functions by conditioning the policy network on a temperature.

 
strength_and_weaknesses: + High impact problem, considering that scheduling is a very generic problem in computer systems.
+ Very solid contribution on how to use GFlowNets in scheduling
+ Solid experiments with good baselines (BRKGA, List Scheduling, GFlowNet)

- Seems to be only simulation (would be great if we can see some real system experiments)

clarity,_quality,_novelty_and_reproducibility: Paper is very well written, clearly explains the problem and its key ideas.
Its experimentations are also very well explained.
summary_of_the_review: The paper works on scheduling of a computational graph which is an NP-hard problem.
The paper considers a problem of scheduling a computational graph on a fixed no. of homogeneous devices.
The paper combines GFlowNet with Topoformer with appropriate changes to the formulation.

While it may look incremental from a cursory look, the paper makes a very solid contribution.
In fact, its experiments also support its significant benefits.

However, it seems that the results are limited to simulation.
It would be great if we can see more real system experiments.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Scheduling operations in a computation graph on parallel hardware is NP-hard. This makes ML approaches such as RL attractive. However, the high cost of evaluation necessitates the use of proxy reward models, which can be overfitted to with reward maximization, resulting in poor performance on actual hardware. This is analogous to drug discovery where a proxy model is used in place of wet-lab experiments.

The solution is to seek not just the best mode in the reward distribution but all modes proportional to their goodness. This can be done by training an amortized sampler which samples proportional to the Boltzmann distribution defined by the EBM (the proxy model). The GFlowNet framework is used to train such a sampler with temperature conditioning. Empirical results show that GFlowNets achieve a higher degree of diversity, which correlates with better on-hardware performance.

strength_and_weaknesses: This paper applies the right tool, GFlowNets, to an important problem, operation scheduling, and obtains good results. Note that it might be worth mentioning that the proposed state space is a DAG, which necessitates the GFlowNet machinery; otherwise, max-entropy RL suffices.

Along the way, it also empirically evaluates the idea of conditional GFlowNets and utilizes a log-partition variance loss, which are not done in prior work.

The presented empirical evidence is comprehensive and includes speedup on target hardware and real-world computation graphs.

Approximating E_s[\zeta(s)] with the mini-batch average of \zeta(s) reminds me of variance reduction via baseline subtraction where the baseline is estimated with the batch reward. I encourage the authors to explore how the proposed loss is related to established variance reduction methods in RL and beyond.

clarity,_quality,_novelty_and_reproducibility: The paper is well-written with few typos or ambiguities.

One of the claimed contributions is the introduction of an alternative to pure reward maximization which is more robust to proxy errors. This might be true for the problem of operation scheduling. It is, however, an established method for other domains, such as drug discovery, where a cheap proxy is used in place of the true reward. In fact, one of the references, Bengio et al., 2021a, uses the exact same rationale in the context of molecule generation. It seems appropriate to point out how this key underlying idea is applied elsewhere.
summary_of_the_review: Well-motivated paper with adequate theoretical and empirical contributions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper examines the computation scheduling problem, recently tackled by RL methods, and attempts to tackle it with the GFlowNet framework. The application is fairly straightforward, but the authors introduce additional interesting aspects that improve performance.

This paper has several contributions:
- applying GFlowNets to the scheduling problem
- training temperature-conditional GFNs (with temperatures sampled log-uniformly)
- training Trajectory Balance-style GFNs without having to estimate $Z(G_C)$ using a variance loss trick
- training on subgraphs as a data augmentation
strength_and_weaknesses: **Strengths**:
- clear writing, clear exposition, clear methods
- brings novel insights into GFlowNet research
- good use of the diversity-as-a-strength feature of GFlowNets to improve scheduling

**Weaknesses**:
- there are some details lacking, for example, I'm not sure what the architecture is to condition on a particular computation graph, or how temperature is fed to the MLP producing $e_\sigma$.
- there are some convincing results for the temperature-conditional GFN method proposed, but not for the log-partition variance loss. The authors claim that learning $Z_\theta(G_C)$ is divergent, but no evidence is provided to help understand the reader why this is the case, nor if the learned flows converge to the correct quantities.
- similarly, the effect of training on subgraphs vs full graphs is not very deeply discussed nor empirically justified.

> To the best of our knowledge, this is the first time that generalization of GFlowNets is tested empirically.

If I understand prior work correctly, generalization to unseen _data_ has been tested (see e.g. [1]). Perhaps here the authors are instead referring to generalization to unseen conditionals (in the present case, unseen computation graphs to be scheduled)?

> In practice, we use the training distribution to estimate $\mathbb{E}_s [\zeta(s)]$ with a mini-batch of trajectories

How does this interface with (temperature and graph) conditioning? $Z$ is effectively a function of $G_C$ and $\sigma$. If I understand correctly this means that for a given $G_C$ (and $\sigma$) many samples are taken. Does this require a "combinatorial" number of samples? i.e. for a "minibatch" of size $n$ do we need $n=n_b n_G n_\sigma$ samples?

[1] Evaluating Generalization in GFlowNets for Molecule Design, Andrei Cristian Nica, Moksh Jain, Emmanuel Bengio, Cheng-Hao Liu, Maksym Korablyov, Michael M. Bronstein, Yoshua Bengio, MLDD 2022
clarity,_quality,_novelty_and_reproducibility: The paper is fairly clear, although there are many details lacking. I am not sure I could exactly reproduce the results of this paper as-is, although probably a fair approximation of it. The paper feels fairly minimal on the empirical side, it has some minimal experiments which are interesting, but it wouldn't hurt for it to be more thorough.

In terms of novelty, the proposed changes are reasonable ways to improve GFlowNets, but as far as I can tell are not groundbreaking ideas.
summary_of_the_review: While I am unfortunately unable to judge the impact of this work on scheduling problems, the proposed improvements to the GFlowNet framework seem interesting. I think the paper could do much more in terms of details, empirical validation of the proposed ideas, and potentially tackle larger scale benchmarks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors apply GFlowNets to the problem of scheduling operations in a computational graph on homogeneous parallel hardware. The evaluate conditional GFlowNets for the first time with the computational graph being the conditioning input and the schedule being the output. They also innovate by conditioning on the reward temperature in order to find a good trade-off between diversity of the generated samples and their average reward. Diversity is important in this application because the generative policy is trained using an imperfect but cheap to compute proxy and only a few of the generated schedules are then evaluated on the ground truth hardware. GFlowNets are interesting in this context because their training objective makes them sample with probability proportional to the reward (rather than maximizing the reward as in other RL approaches). Experiments show improvements against previous methods, including standard RL methods.
strength_and_weaknesses: GFlowNets are a new RL variant (less than a year old) with only a few applications yet, so this paper introduces a new type of application, in the realm of scheduling, and an approach which may be applicable more broadly. The successfully show empirical success on two GFlowNet novelties: conditioning on a rich input (the computational graph) and on temperature (to control the diversity-reward trade-off).

In page 5, they claim that previous works on GFlowNets did not consider the conditional case, but this is not true and they themselves mention in section 4 that Bengio et al 2021b introduced the theoretical framework for conditional GFlowNets. What is true is that may be the first (or among the first, with concurrent work) to validate experimentally a conditional GFlowNet and show its usefulness.


clarity,_quality,_novelty_and_reproducibility: The paper is clearly written, of good quality. Novelty is mostly in the form of experiments and a new application domain for a fairly new method (introduced at NeurIPS 2021). 

summary_of_the_review: This paper introduced a new form of application for GFlowNets, mapping a computational graph to a distribution over efficient schedules for it. To achieve this, the demonstrate the feasibility and success of the conditional GFlowNet formalism and also show how to use it to control the trade-off between diversity and average reward by conditioning on the reward temperature (exponent of the reward).
I consider the paper should be published if they fix their claim about conditional GFlowNets (that it was not considered before, see above).
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper proposes to solve scheduling problems using the recently introduced GFlowNets. Experimental results demonstrate that the method is robust to modeling errors in the proxy metric and can generalize to unseen scheduling problems, somewhat better than earlier ML-based methods in the literature.
justification_for_why_not_higher_score: The experiments are somewhat limited and there is no theory supporting the claims.
justification_for_why_not_lower_score: The reviewers liked the paper which presents a novel solution to an important practical problem.
Decision: Accept: poster