GreenFlow: A Computation Allocation Framework for Building Environmentally Sound Recommendation System

1 Introduction

With the rapid development of AI, especially after the 2012 breakthrough, i.e., the deep learning revolution, computation has grown substantially. The computations required for deep learning research have been doubling every few months, resulting in an estimated 300,000x increase from 2012 to 2018 1 . This significant increase in computation has led to a huge energy consumption and carbon emissions. Facing the explosive growth of the demand for computation, Green AI [Schwartz et al., 2019; Xu et al., 2021; Yigitcanlar et al., 2021], which aims to maximize energy efficiency and minimize environmental impact, has attracted a lot of research interest.

1 https://openai.com/research/ai-and-compute/

RS serves as one of the most widely used AI-based application in various domains, such as content recommenders for multimedia services [Covington et al., 2016], product recommenders for e-commerce [Zhou et al., 2017], or tweet recommenders for social media platforms [Chen et al., 2012]. Due to large-scale and wide-range of RS, it contributes to a large percentage of AI computation. As shown in Figure 1, we show the growth trend of computation in recent years for RSs of an industrial mobile application. The rapidly growing curve poses a great challenge to the computation overhead. However, we found that the difficulty of identifying users' preferences is significantly different, which suggests that the demand for computation of each user is different and an equal allocation strategy would easily lead to an inefficient use of computation. In addition, industrial RSs are often equipped with multiple cascade AI models of varying levels of computation to satisfy the need for low latency (typically within a few hundred milliseconds) and limited computation budget. However, the computation budget allocated to each stage is usually fixed, which also results in inefficiencies.

To maximize the utility of computation consumed by the RS, two critical problems arise in computation allocation: (1) how to estimate the reward curve for each user given different levels of computation; (2) how to allocate the limited computation to arriving requests effectively based on personalized demand. To address these challenges, we propose a computation allocation framework for the industrial cascade RS as shown in Figure 2. Specifically, we first define the two actions that determine the computation as (1) the trained instances of models with different computational complexity; and (2) the number of items to be inferred in each stage. Moreover, we design action chains as the allocation unit, which denote the combinations of model instances and the number of items of all the stages. Next, we estimate a reward score and computation cost for each action chain, followed by a dynamic primaldual optimization considering both the reward and computation budget. This approach results in an optimal action chain for computation allocation.

Scientific Contribution. In summary, our contributions mainly include the following three aspects:

• Problem. We formally define the problem of computation allocation with the goal to maximize its revenue given a limited computation budget in an industrial RS.
• Method. We propose a generic computation allocation framework, which maximizes the revenue of computation through (1) building an personalized reward estimation model of action chains, and (2) conducting dynamic primal-dual optimization for online allocation.
• Evaluation. We perform extensive experiments showing that GreenFlow consistently achieves improvements. By deploying GreenFlow on several industrial RSs, we are able to save approximately 5000kWh of electricity and reduce carbon emissions by 3 tons per day. In addition, we present an evaluation methodology named PFEC, which thoroughly evaluates the effectiveness of the computation allocation method from four aspects: Performance, FLOPs, Energy, and Carbon emission.

Impact to the SDGs. We believe that such a computation allocation framework can greatly improve the resource-use efficiency (SDG 9), which can make the RS environmentally sound and also contributes a lot to the combat climate change (SDG 13) because it can greatly reduce carbon emission without harming the commercial revenue.

2 RelatedWork

2.1 Green AI

Green AI is an emerging research field that aims to develop strategies to reduce energy consumption and mitigate the climate impact of AI systems to maximize energy efficiency. We summarize its research directions as follows:

• Data center: This direction mainly focuses on developing more energy-efficient algorithms and hardware, optimizing data center cooling and power usage [Khosravi et al., 2017], and using renewable energy sources to reduce the power usage effectiveness (PUE).
• Computing cluster and engine: It focuses on improving the conversion efficiency of energy to computation via optimizing the scheduler [Tirmazi et al., 2020], parallel computing [Shukur et al., 2020], and other techniques.
• AI/ML application: Through optimizing the all stages of deep learning [Xu et al., 2021] towards lower computation costs, the conversion efficiency of computation to

revenue is improved. Among existing directions, architecture design [Kitaev et al., 2020; Howard et al., 2017], training [Liu et al., 2021; Huang et al., 2018] and inference [Molchanov et al., 2016; Han et al., 2016] are major research directions.

In this paper, we mainly focus on RS from the perspective of AI/ML application, and achieve the goal of Green AI via allocating the computation in an efficient way.

2.2 Computation Allocation in RS

Multi-stage cascade ranking systems is a common solution in the industry [Wang et al., 2011; Qin et al., 2022] to achieve ranking of a great amount of items with low latency. Its main idea is to deploy simple rankers in the early stages for preranking on the scale of the entire candidate set, and use complex rankers for a much smaller set of items for better accuracy, so that we can achieve a well trade-off between efficiency and effectiveness. To our knowledge, [Jiang et al., 2020] is the first paper to propose the allocation of computation in RS at the granularity of online requests, where the size of candidate items is adjusted for each user. However, this approach only focuses on one specific stage of RS and may not perform well on a cascade architecture. [Yang et al., 2021] extends the method to cascade RS, assuming that the revenue of each stage is independent of the others and can be multiplied to obtain the total revenue of the cascade RS.

However, these studies do not consider the joint effects across stages and different models, which results in a failure to model the personalized reward model at a fine-grained level and allocate the computation effectively.

3 Framework

3.1 Overview

In a multi-stage cascade RS, we introduce the GreenFlow framework to maximize the efficiency of the whole RS under the limited computation budget. Figure 2 illustrates the whole process of a RS after introducing the GreenFlow. In order to take computation budget into consideration, we introduce the new concept called action chain. Since the computation cost of a certain ranking stage is determined by the computational complexity of ranking models and the number of items to be inferred, so that we adopt an action chain to assemble them for all stages. Then, GreenFlow aims to allocate an optimal action chain for each incoming request prior to the RS. In details, the framework is consist of three steps.

In the first step, the action chain generator constructs candidate action chains through cartesian product between models and item scales.

Then, in the second step, we develop a computation measure module and a reward model to estimate the computation costs and rewards of each candidate action chain, respectively. For a comprehensive computation cost estimation, several metrics, such as FLOPs, carbon emissions, and CPU usage, are calculated using static tools (e.g., experimentimpact-tracker 2 , carbontracker 3 , etc.). For the reward estimation task, in the context of a specific request, our model uses the actual revenues (e.g., click rate, conversion rate, etc.) as labels for training. In general, an action chain with a higher computation cost tends to generate better revenue. However, it should be noted that the uplift of the reward curve varies with (1) different requests and (2) the corresponding stages as the computation cost increases.

2 https://github.com/Breakend/experiment-impact-tracker

3 https://github.com/lfwa/carbontracker

In the third step, we propose a hybrid online-nearline architecture to obtain the optimal action chain for allocation under the global computation budget. In the nearline module, a streaming job collects the candidate action chains' reward scores and computation costs of each request. Then, a dynamic primal-dual solver is proposed to do a matching task using the collected samples and the current budget periodically. Finally, the solved dual parameters are stored into an online storage. The entire procedure of updating the dual parameters takes minutes or seconds, depending on the response time requirements of the RS. In the online module, the framework returns an optimal action chain for each arriving request to the RS.

However, it should be noted that introducing GreenFlow into RS will increase the computational overhead. We will further discuss this trade-off in the experiment section.

3.2 EvaluationMethodology

To quantitatively measure the effectiveness of the computation allocation framework in increasing computation utilization and combating climate change, we propose an evaluation methodology named PFEC, which thoroughly evaluates the effectiveness of the framework from the following four aspects, i.e., Performance, FLOPs, Energy, and Carbon emission.

Performance is typically used to measure the revenue generated by RS, with common metrics including clicks, conversions, and other similar measures. FLOPs, which measures how many operations are required to run a single instance of a given neural network, can quantify how much the computation RS consumes.

As for energy and carbon emission, following the method proposed in [Lacoste et al., 2019], we first calculate the energy consumption (EC) mainly taking the RAM, CPU and GPU into consideration:

where PUE is a constant determined by the energy efficiency of a data center (the worldwide average is 1.67 4 ), p(·) and e(·) denote the rated power of certain device and device usage, respectively. With the EC, we can further calculate the carbon emission (CE) via:

where CI is the carbon intensity that varies with different countries, and it is set to 615gCO2ekWh-1 in this paper 5 .

With PFEC, we can compare different allocation frameworks on resource utilization and impact on the environment.

4 Methodology

4.1 Notations and Definitions

In this section, we will introduce the formal definition of the action chain and the computation allocation problem for the whole RS. We assume that x or X denotes a scalar; ⃗x denotes a vector; X denotes a matrix; and X denotes a set.

Let It := {1, 2, ..., It} be a set of arriving requests in time t, K be the number of stages in the cascade RS and C be the computation budget of the whole RS. In each stage k, the ranking model mk and ranking item scale nk are selected from the Model Pool M and the Item Scale set N as shown in Figure 2, respectively. A tuple of mk and nk constitute the key parameters sk = {mk, nk} of the k-th stage. Then, we define the action chain of a whole cascade ranking RS as a = (s1, s2, ..., sK) and let A be the action chain set constructed by the action chain generator where |A| = J . For each action chain aj, let cj be the estimated computation cost. For each request i, let Rij := R(aj, fi) be the estimated reward of aj with the context feature fi which is related to the arriving request i ∈ It. Then we define the allocation strategy xi := (xi,1, xi,2, ..., xi,J) ∈ {0, 1}J that xij represents the decision variable of allocating action chain j to request i. We construct the computation allocation problem as following:

4 https://journal.uptimeinstitute.com/is-pue-actually-going-up/

5 https://app.electricitymaps.com/zone

In the next two subsections, we first introduce how to accurately estimate the reward function Rij , and then propose a method for quickly solving the Problem (3).

4.2 Personalized RewardModel

In general, increasing computation is likely to result in higher revenue. However, the same action chain may generate different revenues for different requests. Thus, for each request i with context features fi and action chain aj, it is necessary to design a personalized model to accurately estimate the reward Rij. In this regard, we encounter the following three challenges:

• How to model the dependence of cascade stages in RS?
• How to deal with the data sparsity problem?
• How to ensure the monotonicity between computation and reward?

Accordingly, we introduce the key three mechanisms of the model in the remainder of this section.

Recursive Multi-Stage Design. The structure of our proposed model is designed in a recursive style to match the cascade design of RS. As illustrated in Figure 3, the chunk of neural network is the detailed implementation of the recursive function gk. Given the output embedding of the previous stage ⃗hk-1, the action {mk, nk} from k-th stage, and the context feature fi, gk outputs the reward uplift ∆rk and ⃗hk for the next stage. Hence, Rij is calculated by:

where K is the number of stages; ⃗ fi, ⃗mk, ⃗nk are the encoded embeddings of fi,mk, nk, respectively. Meanwhile, each gk should deal with data sparsity problem and obey the monotonicity constraint.

Multi-Basis Functions

In an industrial RS, collecting feedback for all action chains on the same user can be expensive, which presents a challenge in learning the function gk using a network with high degrees of freedom. So we propose a novel structure of consisting multi-basis functions in the yellow chunks of Figure 3. The reward uplift ∆rk is given by:

where B is a set of basis functions and |B| = P, 1Q is a vector of all ones; wp ∈ ⃗w = (w1, w2, ..., wP ) and vp ∈ ⃗v = (v1, v2, ..., vP ) are two vectors calculated by the feedforward neural networks FNN(·) in the green chunk of Figure 3. ⃗w and ⃗v are defined as:

where Q is the dimension of the embedding ⃗nk and ∗ is the element-wise multiply. In the current implementation, we define the multi-basis functions set as:

This design has the following advantages:

• The use of multi-basis functions can better capture the reward curves of users with varying levels of activity.
• The design of different basis functions can make the reward model obtain different mathematical properties. For instance, if the second derivative of the basis functions we design is non-positive, then the marginal revenue of the reward curves will be non-increasing. That is, as FLOPs become larger, the slope of the reward curve will become smaller.

In the experiment section, we will conduct ablation experiments to demonstrate the advantages of the aforementioned design and the specific effects it achieves.

Monotonic Constraint. To obey the monotonicity between computation (especially the item scale nk) and reward ∆rk, we use a multi-hot embedding ⃗nk for the item scale nk in each stage k. In the multi-hot encoding module, the item scale set Nk is divided into Q groups and each nk in the same group shares the same embedding. The larger item scale nk attains more 1s in ⃗nk during the encoding process, and the larger ⃗v computed by Equation (6) will be. Since all the basis functions are monotonically increasing and ⃗w are non-negative, the monotonically increasing relationship between the item scale nk and reward ∆rk is preserved.

4.3 Dynamic Primal-Dual Optimization

With known requests It, estimated revenues Rij and resource cost cj in time t, one can regard the problem defined in Equation (3) as a bipartite matching problem [Aggarwal et al., 2011] following a primal-dual framework. By optimizing this problem, the dual variables can be solved directly. Specifically, the Lagrangian function of Equation (3) is given by

and the dual form of Equation (3) leads to:

where λ is the dual variable. In the literature of matching problem, λ is called dual price which represents the increased revenues of per resource cost given the budget. With the help of strong duality and K.K.T conditions, we can derive the optimal decision ⃗xi from solved dual price λ∗ by:

We propose a dual descent algorithm to solve the optimal dual price λt in time t and apply the λt to make the online decision ⃗xi for requests i ∈ It+1 periodically. The pseudocode of the whole procedure is summarized in Algorithm 1. In each time t, a gradient descent approach is adopted to solve λt+1 by step 6∼8 with global convergence guarantee [Li et al., 2020]. Moreover, [Agrawal et al., 2014] shows that the online decision in time t + 1 using the previous λt is nearoptimal when the requests adopt a stochastic arriving model and the requests It is enough for solving λt. By adopting a seconds or minutes period of Algorithm 1 in an industrial RS, our algorithm is effective that the distribution of arriving users is i.i.d. in a short time and the number of requests per second are generally thousands.

5 Experiments

In this section, we will evaluate the proposed framework through various offline and online experiments to demonstrate its effectiveness. Before introducing the experimental results, we will first describe the experiment settings, including the datasets used, details of training, comparison methods, and evaluation metrics.

5.1 Experimental Setup

Dataset. For reproducibility, we use one public dataset named Ali-CCP 6 for offline evaluation. It is a public click

6 https://tianchi.aliyun.com/dataset/408

Algorithm 1 Dynamic Primal-Dual Algorithm

• 1: Input: computation budget C, action chain set A, computation cost cj (∀aj ∈ A), max iterations L, step size η and initialized dual price λ0.
• 2: for t = 1, 2, . . . do
• 3: Collect the reward Rij for each request i ∈ It.
• 4: Let λ0t = λt-1.
• 5: for l = 0, 1, 2, ..., L do
• 6: Update ⃗xi, ∀i ∈ It given λlt by Equation (10).
• 7: ∇L = C - ∑i∈It,1≤j≤J cjxij.
• 8: λl+1 t = λlt - η∇L.
• 9: end for
• 10: Let λt = λLt , and solve ⃗xi for i ∈ It+1 with λt by Equation (10).
• 11: end for

and conversion prediction dataset collected from traffic logs of Taobao's RS [Ma et al., 2018], and consists of 85 million samples. We randomly sample 50% of users in the dataset for training models in the cascade RS, 25% for building the validation dataset, 22.5% for training sample generation of the reward model, and the rest 2.5% for the final evaluation, which includes 9016 users.

Implementation of Action Chain. In the experiments, we consider a three-stage (i.e., recall, pre-ranking and ranking) cascade RS with four trained instances of models for allocation, of which detailed statistics are shown in Table 1. To simplify the comparison, only one model for each of the first two stages, which are DSSM [Huang et al., 2013] and YoutubeDNN [Covington et al., 2016] (abbreviated as YDNN for brevity), respectively. DSSM is used for ranking the entire candidate items (its size is n1), and YDNN performs pre-ranking on the top-n2 scored candidate items ranked by DSSM. As for the ranking stage, the most two powerful models, DIN [Zhou et al., 2017] and DIEN [Zhou et al., 2018], are available for selection to generate top-n3 scored candidate items feed by the previous stage. Finally, we choose top scored items to expose to users. Therefore, an action chain is denoted as a = ({YDNN, n2}, {DIN or DIEN, n3}), where n2 ∈ N2 = [800, 900, 1000, ..., 1500] and n3 ∈ N3 = [60, 80, 100, ..., 200] in this paper ({DSSM, n1} is omitted due to its fixed computation cost).

Evaluation Metrics. To compare different methods thoroughly, we construct various computation budgets C by simulating different action chains. Given a specific budget constraint C, we focus on the following offline metrics:

where P denotes the top-e scored candidate items in the ranking stage generated by an action chain (we set e = 20 in this experiment), and the reward ˆRij of the user i is set to the number of the clicked items. Since it is difficult to simulate the energy consumption in an offline way, we mainly consider the first two indicators of PFEC, i.e., revenue@e and C, in the offline experiments, and a full PFEC evaluation is conducted on the online experiments.

Training Sample Generation of Reward Model. To train the personalized reward model, we simulate different action chains for each user and calculate the reward of each action to build the training dataset. Specifically, the click-through rate on P is used to represent the reward (i.e., label) of the action chain a = ({YDNN, n2}, {DIN or DIEN, n3}) for supervising the training of the reward model.

Comparison Methods. Two methods are compared in the experiments:

• EQUAL: Computation is allocated to each user equally based on a given fixed action chain.
• CRAS [Yang et al., 2021]: A method that decomposes the computation allocation into independent subproblems on each stage of RS.

5.2 Offline Experiments

In this part, the offline experiments are designed to answer the following questions:

• Q1: Does our proposed GreenFlow outperform other approaches on the task of computation allocation?
• Q2: Does multi-stage modeling in reward estimation outperform single-stage modeling?
• Q3: Is it necessary to provide multi-models in one stage for allocation rather than single-model?
• Q4: How does each variant of the proposed reward model contribute to the improvement?

Q1: Effectiveness of GreenFlow

We report the results given different computation budgets in Figure 4. Due to the limitation that EQUAL and CRAS only consider single model for allocation in the same stage, we design two variants of EQUAL and CRAS, respectively, i.e. EQUAL-DIN, EQUAL-DIEN, CRAS-DIN and CRASDIEN, for comparison as there are two available models in the ranking stage. From Figure 4, we can draw the following conclusions:

• With the decreasing budget, the number of clicks is accordingly decreasing, which implies that a welldesigned cascaded RS is necessary due to its improvement over the revenue of computation.
• Our proposed method outperforms all baseline methods with a large margin, which verifies the superiority of dynamic action chain and multi-stage reward modeling.

Q2: Single-Stage vs. Multi-Stage

To demonstrate the effectiveness of multi-stage modeling, we compare GreenFlow and CRAS with one action fixed, i.e., our reward model degrades into single-stage. From Table 2, we observe that CRAS and GreenFlow achieve comparable performance under one action fixed, but GreenFlow outperforms CRAS by a large margin when conducting multi-stage modeling, which verifies the superiority of multi-stage modeling.

Q3: Single-Model vs. Multi-Model

As presented in Table 1, both DIN and DIEN models have similar FLOPs and perform comparably in terms of AUC. This naturally raises the question of whether introducing different models in the same stage is necessary. We argue that this necessity based on the fact that no single model can outperform all others on all users. To evaluate this, we divided the user set into three groups: those better suited to DIN, those better suited to DIEN, and those equally suited to both. The distribution of these groups is approximately 1:3:6, respectively. Then, we conducted three tests on GreenFlow using only DIN, only DIEN, and both of them. The results are shown in Table 3, and it is evident that using multiple models yields gains ranging from 1% to 6% on revenue@e compared to using any single model.

7.5

1471

1823

1848

8.7

1581

2007

2026

10.1

1686

2079

2181

Table 3: Results of GreenFlow with different models available for

selection in the ranking stage.

Variants of Reward Model Metrics

Recursive

Mechanism Multi-Basis Functions Field-RCE revenue@e

�

�

�

�

�

�

�

�

0.137

2174

0.148

2082

0.150

2065

0.177

1875

Table 4: Results of variants of reward models under 9.96 × 1012

FLOPs.

Q4: Variants of Reward Modeling

To verify the effectiveness of the proposed reward model, we

test different combinations of the two mechanisms (i.e., the

recursive mechanism and the introduction of basis functions)

in the reward model. Since well-calibrated models are im-

portant for optimizing Equation (3), we additionally intro-

duce another metric for evaluating the reward model, which

is field-level relative calibration error [Pan et al., 2019]:

Field-RCE = 1

∑

f∈F

|D|

yi)|

| ∑i∈Df (yi - ˆ

1

|Df |

∑i∈Df yi

where D is the test dataset, F is the specified feature field, Df

is the set whose feature value is f, yi is the label and ˆ

yi is the

predicted value. This metric measures the deviation between

the predicted value of reward curve and posterior probability.

Table 4 shows the results, and we conclude that both recur-

sive mechanism and multi-basis functions contribute to im-

provement of Field-RCE and revenue@e.

5.3 Online Experiments

To further demonstrate the effectiveness of GreenFlow, we conduct online A/B testing on three RSs with different levels of computational overhead, and the results are reported in Table 5. We observe significant decrease in FLOPs (i.e., greatly reduce the demand for model inferring servers), a slight improvement in the accuracy of RS, and negligible latency due to the introduction of GreenFlow. Specifically, we report the extra computation cost and latency brought by GreenFlow in Table 5, which can be ignored compared to the RS. Note that for RS A, the latency even decreases because the large reduction in FLOPs leads to fewer request packets, greatly reducing the time of model inference.

,

(12)

CO2

-2995kg

-103kg

-76kg

Extra

Cost Latency

-20ms +10ms

+5ms

FLOPs

+3% +8% +8%

Table 5: Online A/B testing results (per day) of three RSs.

Due to a large number of requests, it is also necessary to ensure that the constraint of the computation budget can be precisely satisfied in an industrial environment. When it fails, RS cannot meet all requests for recommendation and has to resort to computation downgrade, resulting in harm to revenue. In Figure 5, we show computation cost of three different allocation strategies, and conclude that GreenFlow can handle traffic spikes well under the constraint of the computation budget and save a lot of computation in the same time.

To date, GreenFlow has been deployed in several RSs of an industrial mobile application with about one billion users for one year. This deployment has resulted in a significant reduction of 1,000 tons of carbon emission and a saving of approximately 2,000,000 kWh of electricity. Moreover, GreenFlow has achieved a remarkable balance among revenue, computation, carbon emission, and energy consumption.

6 Conclusion

In this paper, we propose a computation allocation framework for industrial RS to enhance resource utilization efficiency. The framework first estimates a reward score for each action chain, and dynamic primal-dual optimization is conducted to search for the optimal action chain while considering both the reward score and computation budget. Through offline experiments and online A/B testing, we demonstrate the effectiveness of GreenFlow in maximizing the revenue of a RS given a particular computation budget. Additionally, GreenFlow has been deployed in the production environment of a mobile application, resulting in significant economic returns and a substantial reduction in carbon emissions. In the future work, we will focus on improving the reward model since it serves as the core component that determines the computation allocation.

Contribution Statement

Xingyu Lu and Zhining Liu contributed equally to this research. Hongxuan Zhang completed this work at Ant Group.