BOA Constrictor: Squeezing Performance out of GPUs in the Cloud via Budget-Optimal Allocation Zhouzi Li, Cindy Zhu, Arpan Mukhopadhyay, Mor Harchol-Balter, Benjamin Berg Abstract . The past decade has seen a dramatic increase in demand for GPUs to train Machine Learning (ML) models. Because it is prohibitively expensive for most organizations to build and maintain a large GPU cluster, organizations instead choose to rent GPUs from cloud providers. The customer is responsible for devising a policy for (i) deciding how many GPUs to rent at every moment in time to process a stream of ML training jobs and (ii) allocating the rented GPUs among the currently active jobs in the system. Because ML training jobs can be parallelized across different numbers of GPUs, the customer generally has many options for how many GPUs to use for each job. Allocating more GPUs to a single training job will cause the job to complete more quickly. However, the customer pays for each GPU-hour they use, and a training job receives a diminishing marginal benefit from running on additional GPUs. Hence, allocating too many GPUs to a single training job can dramatically increase the overall cost that the customer pays to the cloud provider. This gives rise to a cost-performance tradeoff that customers must balance when running training jobs in the cloud. To balance the cost-performance tradeoff, we develop BOA Constrictor, a new scheduler for ML training jobs which uses a Budget-Optimal Allocation (BOA) policy to squeeze the highest level of performance out of a cloud-deployed GPU cluster given a fixed budget constraint. While prior approaches have focused on either fixed-sized clusters and heuristic approaches for balancing cost and performance, we explicitly formulate the problem as a budget-constrained scheduling problem. In our stochastic model, the user has a time-average monetary budget that they are willing to spend on training. This translates to a constraint on the time-average number of GPUs that can be rented. We derive the BOA policy, which minimizes the average job completion time (JCT) of a stream of arriving jobs subject to the user’s budget. Our BOA policy can be computed efficiently for any budget level and therefore provides users with the optimal tradeoff between cost and performance. For a given budget level, we demonstrate that BOA Constrictor can reduce average JCT by 1.6 × 1.6\times in small-scale implementation experiments and by 2 × 2\times in detailed, large-scale simulations compared to state-of-the-art heuristic based schedulers. Furthermore, in both simulation and real-world experiments, BOA Constrictor reduces the budget needed to achieve a given average JCT by up to 2 × 2\times . 1. Introduction The explosion in Machine Learning (ML) over the past ten years has led to a dramatic increase in demand for GPUs to train ML models ( jouppi2017datacenter ) . Because it is prohibitively expensive for many organizations to build and maintain a large GPU cluster, hyperscale cloud providers (Microsoft Azure, Amazon AWS, Google Cloud) have seen explosive growth in demand for renting cloud-based GPUs. For example, Amazon’s profit from renting GPUs and related infrastructure is expected to grow to 20 billion dollars by 2026, roughly 20% of the profit currently generated by AWS ( gpureport ) . (a) Average JCT vs. operating budget. (b) P95 JCT vs. operating budget. Figure 1 . Our solution, BOA Constrictor balances the cost-performance tradeoff for training in the cloud. While existing policies such as Pollux ( qiao2021pollux ) do not explicitly balance the cost-performance tradeoff, BOA Constrictor provides up to a 2\times improvement in average JCT and up to a 3\times improvement in P95 JCT for a given budget by deriving a budget-optimal allocation policy. This trend makes the question of how cloud customers can efficiently train ML models using cloud-based infrastructure one of the most important problems facing the computer systems community ( subramanya2023sia ; qiao2021pollux ; moritz2018ray ; misra2021rubberband ) . In this cloud computing paradigm, the customer is responsible for devising a rental policy that decides how many GPUs to rent at every moment in time ( salvaris2018microsoft ) . The customer may be an individual developer or researcher, or an organization such as a company or research lab that rents a pool of GPUs to serve a stream of ML training jobs. The customer submits a stream of training jobs to their cloud-based cluster, and is charged on a pay-for-what-you-use basis according to a set fee per GPU-Hour of usage. The customer may increase or decrease their rental demands dynamically over time to both suit the performance needs of their workloads and control costs. Specifically, renting additional GPUs may decrease job completion times (JCT, also known as response time). The cloud provider, in turn, aims to quickly allocate GPUs to customers. As a result, cloud-based GPU instances can generally be rented or returned on a timescale of 1 - 2 minutes, making it feasible for customers to scale the size of their cloud deployments frequently in response to changes in their workloads. This raises the question of what rental policy a customer should employ to balance a tradeoff between achieving good performance and limiting the costs paid to the cloud provider. While the cost-performance tradeoff has been considered extensively in the context of ML inference workloads, where the problem closely resembles the traditional autoscaling problem, there has not been similar attention paid to devising rental policies for serving ML training workloads. Crucially, training jobs are long-running (on the order of hours, or longer, depending on the model) and can be configured to run in parallel across different numbers of GPUs. Hence, a customer must decide not only how many GPUs to rent in total at each moment in time, but also how to divide those GPUs across the jobs currently in the systems. These decisions must be made online as training jobs arrive and complete, incorporating potential overheads of preemption, and of rescaling the cluster size while jobs run. The problem is further complicated by the fact that the performance characteristics of jobs change over the course of training. Training jobs receive sublinear speedup. Modern ML training jobs can be parallelized across multiple GPUs to complete training more quickly. Running on additional GPUs provides a job with additional compute and memory that can be exploited by a variety of parallel schemes (e.g., model parallelism, tensor parallelism, pipeline parallelism, see Section 2.1 ). However, the benefits of parallelism are generally limited by a combination of sequential bottlenecks, synchronization overheads, and statistical inefficiency (see Section 2.1 ). As a result, training jobs generally receive a diminishing marginal benefit from running on additional GPUs. This effect is commonly measured via a job’s speedup function , s(k) , which describes how much faster a job can train a model to a given level accuracy on k GPUs as opposed to some base configuration, in our case one GPU. Due to the aforementioned limits to parallelism, a training job’s speedup function is generally sublinear and concave. (a) Speedup functions (b) Training cost Figure 2 . Performance of a Cifar10 training job on different numbers of GPUs. Changes to job hyperparameters over the course of training cause a job’s speedup function to shift. Because the speedup functions are concave and sublinear, training costs increase when the job is parallelized on a larger number of GPUs. Sublinear speedup functions have a particular impact on the GPU rental problem where cost is a first-order concern. If a job received a linear speedup from parallelism, it could run on k GPUs and complete in \frac{1}{k} th the time, meaning that the total GPU usage would remain constant. However, because jobs receive a sublinear speedup, a job run on k GPUs will complete in \frac{1}{s(k)} as much time, leading to a factor \frac{k}{s(k)} increase in the number of GPU-hours required to complete the job (Figure 2(b) ). Hence, customers who aim to run training jobs on a flexible pool of cloud resources must balance a tradeoff between completing jobs more quickly and paying a higher cost to the cloud providers. Training jobs and training workloads change over time. Balancing the cost-performance tradeoff for cloud-based ML training is particularly challenging because the problem is dynamic along several dimensions. First, a job’s speedup function may change over the course of training (see Figure 2(a) ) as the optimal choice of job hyperparameters changes (see Section 2.1 ) ( qiao2021pollux ; zhang2025rubick ; subramanya2023sia ) . It may be possible to improve cost or performance by adapting allocation decisions as job speedup functions change. Second, a customer does not deal with a single job, but rather a stream of training jobs that are submitted over time. Each job may have a different speedup function that changes as the job runs. As a result, the composition of the training workload may shift over time. Examination of publicly available traces shows that job arrival times are highly-variable, showing significant bursts and changes in the relative frequency of different model types and sizes (see Section 2.3 ). Notably, the common modeling assumption of arrivals following a time-homogeneous Poisson process is a poor reflection of reality. In summary, a good GPU rental policy must respond to changes both in the speedup functions of individual jobs, but also bursts and compositional changes in the overall workload. Balancing cost and performance. Because GPUs are being rented from a flexible pool of cloud resources, the customer has broad latitude to adjust the cluster size to adapt to these shifts. For example, it might be beneficial to increase the number of rented GPUs when the jobs in the system enter phases with higher speedup functions, or when there is a burst of highly-parallelizable training jobs, since these jobs can efficiently utilize a high number of GPUs in parallel. Likewise, given a small number of jobs with flatter speedup functions, it may be beneficial to decrease the total number of rented GPUs in order to control costs. To balance the cost-performance tradeoff, the customer must make two principal decisions: (1) How many GPUs to rent from the cloud provider at every moment in time? (2) How to divide the rented GPUs among the training jobs currently in the system? The customer must answer these questions in real time as jobs arrive and depart from the system. As we will detail in Section 2.4, existing schedulers address at most one of the above questions . Furthermore, prior approaches have the added drawback that they generally make use of scheduling heuristics to set job allocations rather than using mathematical analysis to provide performance guarantees. As a result, there is no analysis of the average JCT in existing systems, and no mechanism for weighing how changes in the cluster size will affect performance. Our Solution: BOA Constrictor. This paper presents BOA Constrictor , a scheduling framework for cost-efficient cloud-based training of ML models. To control costs, the customer provides BOA Constrictor with an operating budget , the long-run average number of GPU-hours they wish to expend per hour. Given a stream of training jobs, BOA Constrictor determines (i) the overall cluster size and (ii) how to allocate the rented GPUs to each job in the system. Based on the customer’s budget and the overall workload composition, BOA Constrictor minimizes the average job completion time (average JCT) across jobs. For example, the customer might aim to spend $10,000 per month on training, which is equivalent to maintaining an average cluster size of 40 GPUs. Over the course of a day, BOA Constrictor will adjust the cluster size and job allocations. Note that both of these rescaling actions come with overheads, so BOA Constrictor must limit the frequency of these changes. The core of BOA Constrictor is our Budget-Optimal Allocation policy (BOA), which minimizes average JCT subject to an arbitrary budget constraint under a very general model of the system. The mathematical analysis behind the BOA policy also allows the customer to use BOA Constrictor to derive the entire cost/performance Pareto frontier (see Figure 1 ), providing a useful tool for the customer to trade off cost and performance. Contributions The contributions of this paper are as follows: We begin by proving new theoretical results for optimally solving the GPU rental problem that advance the current theoretical understanding of scheduling for parallelizable jobs. Specifically, • We consider the GPU rental problem from the perspective of a cloud service customer who has a budget on the long-run average number of GPU-hours consumed per hour. The customer wants the best possible performance for their money, and therefore aims to minimize the average JCT across a stream of jobs while adhering to the budget. In our model (Section 3 ), job sizes and interarrival times can follow very general distributions. Job speedup functions are permitted to change from job to job and change over time for a single job. We solve the GPU rental problem for this extremely general setting in Section 4 . We refer to our optimal policy as the Budget Optimal Allocation (BOA) policy. While this paper focuses on the homogeneous GPU setting, our theoretical results can be easily generalized to the heterogeneous GPU setting, see Appendix E . After proving these theoretical results, we implement BOA Constrictor, a cluster scheduler that leverages the BOA policy. We evaluate our BOA Constrictor implementation using real-world experiments on ML training jobs, as well as extensive, detailed simulations. • We implement BOA Constrictor on top of the AdaptDL framework ( adaptdl ) (Section 5 ). Using both our implementation and a detailed ML training simulator, we evaluate BOA Constrictor using a production trace of ML training jobs (Section 6 ). • To aid in our comparison, we implement a variant of Pollux which uses goodput-based autoscaling as originally proposed in ( qiao2021pollux ) . No working implementation of this idea existed previously, and implementing Pollux with autoscaling was a significant development effort (see Section 6 ). We compare with Pollux ( qiao2021pollux ) because it not only optimizes for JCT, but also dominates several other proposed system that attempt to reduce job JCTs (see Section 6.1 ). • BOA Constrictor implements the BOA policy in a way that decouples the optimization computation from the policy execution (see Section 5.2 ). This allows us to run the optimization computation primarily offline, with only very negligible overhead on the critical path of job scheduling (see Section 5.4 ). • For a given budget, BOA Constrictor improves average JCT by up to a factor of {\sim}1.75\times in implementation (Figure 1 ). Additionally, for a given average JCT, we can reduce the budget needed to achieve this level of performance by up to a factor of {\sim}2.2\times . Crucially, BOA Constrictor makes very different scheduling decisions than state-of-the-art policies by relying on our theoretical models instead of intuitive scheduling heuristics (see Section 6.4 ). 2. Background This section describes the current state-of-the-art in training ML models in the cloud. We describe how modern ML training jobs can be dynamically configured to leverage multiple GPUs (Section 2.1 ), why training workloads require dynamic scheduling and autoscaling policies (Sections 2.2 and 2.3 ), and how state-of-the-art approaches for scheduling training jobs fall short both in theory and in practice (Section 2.4 ), revealing the need for a theoretically-grounded policy that optimizes the cost-performance tradeoff as a primary concern. 2.1. Distributed Training in the cloud To accelerate the ML training process, training jobs are typically distributed across multiple GPUs in parallel. However, making efficient use of a set of GPUs to accelerate training requires careful configuration of the training job to avoid excessive overheads. Exploiting parallelism in distributed training. A single job can exploit parallelism in two central ways. First, data parallelism involves replicating a full model across many GPUs and dividing batches of training data across these replicas to process a higher number of samples in parallel per unit time. Second, model parallelism involves spreading parts of a single model instance across multiple GPUs, either by partitioning different layers of the model onto separate GPUs (pipeline parallelism) or splitting a single tensor of model weights across multiple GPUs (tensor parallelism). In this paper, we consider jobs that are configured to use data parallelism, although this assumption is not core to our results. This choice is made to ease comparison with the relevant prior work. As described in ( qiao2021pollux ) , data parallel training jobs experience two main overheads from parallelization. First, these jobs periodically synchronize with a parameter server in order to compute gradients; this prevents the job’s throughput (i.e., the number of training examples processed per second) from scaling linearly with the number of GPUs occupied by the job. Second, computing gradients on higher numbers of GPUs in parallel requires larger batches of data to be processed between gradient updates, reducing the training efficiency , defined as the amount of accuracy the model gains per training sample ( qiao2021pollux ) . Combined, these effects give rise to the characteristic sublinear speedup function measured for the data-parallel jobs in Figure 2(a) . Similar overheads produce similarly sublinear speedup functions when different modes of parallelism are used ( zhang2025rubick ) . There are also various proposals for sharing GPUs between multiple training jobs via software or hardware based mechanisms ( awsMIG ) . The BOA policy we derive can be easily be adapted to handle physically partitioned GPUs (e.g., NVIDIA Multi-instance GPUs), but evaluating our BOA Constrictor implementation under these conditions is outside the scope of this paper. Hyperparameter selection. Training jobs expose a vast array of hyperparameters that can be tuned to control the performance characteristics of the training process. These hyperparameters range from specific training algorithm parameters such as learning rate and batch size ( qiao2021pollux ) to higher-level decisions such as the mode of parallelism ( zhang2025rubick ) or the type of model being trained. The choice of hyperparameters can significantly affect the speed of training ( li2018hyperband ) , but finding the optimal configuration is known to be difficult. Nonetheless, techniques such as Bayesian optimization and multi-armed bandit theory have been used to explore the hyperparameter space and efficiently find configurations that lead to shorter training times. Recent works have noted that the choice of a degree of parallelism affects the optimal choices of other hyperparameters (e.g., optimal batch size depends of the degree of parallelism ( qiao2021pollux ) ). Several papers have suggested intertwining the hyperparameter search process with the scheduling algorithm that chooses the degree of parallelism for each job ( qiao2021pollux ; subramanya2023sia ; zhang2025rubick ; misra2021rubberband ; dunlap2021elastic ) . It is not clear, in general, how much of the improvement reported by these works comes from hyperparameter optimization versus improved scheduling. We observe that the existing systems tend to leverage highly-sophisticated hyperparameter search techniques in combination with overly simplistic scheduling heuristics. This suggests that there is significant room for improvement solely by optimizing the scheduling aspect of these systems. We therefore focus on the scheduling aspects of the GPU rental problem rather than hyperparameter search. In our theoretical modeling and implementation results, we assume that for every job, a hyperparameter search process has discovered a good configuration to use with each possible number of GPUs. In other words, the speedup functions considered in our model represents the speedup a job receives given a set of hyperparameters that have been optimized for that degree of parallelism. We show in Section 6 that, even when we control for the effects of hyperparameter optimization, we achieve an {\sim}2\times improvement in cost or performance compared to existing systems. This improvement comes solely from improving the scheduling policy that sets the degree of parallelism for each job and the overall cluster size. We also show via simulation in Section 6 that BOA Constrictor maintains its advantage when hyperparameters such as batch size and learning rate are adaptively tuned in the background by a separate hyperparameter selection process. 2.2. Metrics Once a job’s hyperparameters have been selected and the job has been allocated a set of GPUs to run on, we measure the job’s performance along three dimensions. The first is accuracy , which we measure as the training loss with respect to a customer-defined loss function. We assume that each job is submitted with some desired level of accuracy that the customer wishes to attain. We refer to a job’s size as time required to attain a desired level of accuracy using a single GPU. We measure the job completion time (JCT), which is the time from when the job arrives to the system until it attains the desired level of accuracy and departs the system. Finally, we can measure a job’s resource consumption , the number of GPU-hours expended during training. 2.3. Workloads To understand why modern training workloads can benefit so greatly from improved scheduling on flexibly-sized clusters, one must consider the composition of modern training workloads. We observe that these workloads exhibit notable variability along several dimensions. This not only suggests that improved scheduling will greatly benefit average JCTs, but underscores the importance of avoiding overly restrictive modeling assumptions when trying to derive optimal GPU allocation policies. We note three main sources of variability based on the traces reported in ( qiao2021pollux ; subramanya2023sia ) . (1) Job sizes are highly-variable. Given some fixed number of GPUs, the time required to complete a training job can vary by more than an order of magnitude depending on the type of model being trained and the level of accuracy the customer requires. Notably, assuming exponential job sizes is an unrealistic modeling assumption in this case. Improved scheduling policies are known to reduce queueing times when job sizes are highly-variable ( harchol2013performance ) . (2) Job arrivals are bursty. Jobs experience several bursts of arrivals over time. Hence, modeling arrivals via a stationary Poisson process is an unrealistic modeling assumption. Leveraging cluster autoscaling can reduce the effects of variability in the arrival process ( gandhi2012autoscale ) . (3) Job speedup functions change over time. The speedup a job receives from parallelization depends on both the job’s throughput and efficiency. As noted in ( qiao2021pollux ) , job efficiency tends to be lower at the beginning of training. As a result, job speedup functions tend to shift upwards over the course of training. Hence, assuming that jobs follow a single speedup function for their entire lifetime is an unrealistic modeling assumption. For a full description of the workloads used in our evaluation, see Section 6.1 . These observations about training workloads suggest that systems could benefit from more complex, theoretically grounded allocation policies. However, we also find that training workloads violate the exponentiality and independence assumptions commonly made by the performance modeling community. 2.4. Prior Work: Current Schedulers Fall Short Prior theoretical work has separately considered the problem of scheduling parallelizable jobs ( berg2018 ; berg2020hesrpt ; berg2022case ; berg2020optimal ) and autoscaling ( gandhi2012autoscale ; gandhi2011distributed ; psychas2022theory ) , but we are not aware of any work which considers both problems simultaneously to balance the cost-performance tradeoff. By developing a stochastic model of this problem and solving for the BOA policy in Sections 3 and 4 , we can show how real-world systems can benefit by optimally balancing the cost-performance tradeoff. These existing systems fall broadly into one of three categories. Approach 1: Reservation-based systems. Reservation-based schedulers like Ray ( moritz2018ray ) and Tiresias ( gu2019tiresias ) and others ( hu2023lucid ; xiao2020antman ) ask the customer to specify the GPU requirements of each of their jobs. For these systems, the goal is to provide the resources demanded for each job as quickly as possible. To this end, Ray uses very simple heuristics related to data locality and load balancing, but does not explicitly aim to minimize the average JCT across jobs. Tiresias recommends using the Gittins index as a scheduling heuristic, ignoring the fact the Gittins index is suboptimal when scheduling multiserver jobs unless the system load is extremely heavy ( scully2020gittins ) . Ray allows autoscaling, while Tiresias does not, but all reservation-based systems inherently defer the cost-performance tradeoff to the customer and provide no decision support in how to set GPU requirements for different training jobs. Moreover, relying on customer-generated reservations also prevents the system from changing job allocations to respond to changes in a job or the overall workload. Approach 2: Policy-based allocation with a fixed cluster size A wide variety of recently proposed systems try to improve performance by a combination of hyperparameter tuning and dynamic GPU allocation ( zhang2025rubick ; qiao2021pollux ; subramanya2023sia ; zheng2023shockwave ; li2023easyscale ; gu2023elasticflow ; mahajan2020themis ; narayanan2020heterogeneity ; le2020allox ) . While approaches differ in exactly how job configurations are tuned, which heuristics are used, and which performance metrics are optimized (e.g., makespan, JCT, or fairness), these systems are similar in their high-level goals of choosing GPU allocations to optimize overall performance across a stream of training jobs. All prior work only considers a fixed-size cluster (except for ( qiao2021pollux ) , which will be discussed in Approach 3). In this paper, we choose to compare with Pollux ( qiao2021pollux ) , because it has been shown to dominate the JCT of most of the above policies. For example, Pollux dominates the reservation-based approach of Tiresias ( gu2019tiresias ) even when job allocations are chosen by an offline optimizer. Additionally, Pollux dominates Optimus ( peng2018optimus ) even when Optimus is given an oracle to optimally select job hyperparameters. More recently, Lucid ( hu2023lucid ) was shown to only outperform Pollux at very high loads. Hence, by showing that BOA Constrictor outperforms Pollux at all budget levels , we also demonstrate that BOA Constrictor compares favorably to a wide range of systems designed to schedule training jobs in fixed-size clusters. More detail about Pollux is given in Section 6 . Approach 3: Policy-based with autoscaling To the best of our knowledge, ( qiao2021pollux ) is the only prior work that mentions scaling the cluster size jointly with job allocations. While Pollux is designed to use fixed-size clusters, the authors do propose a Pollux variant that scales the cluster size to maintain a given level of cluster efficiency ( ( qiao2021pollux ) refers to this as goodput-based autoscaling). However, the authors only evaluate their proposed idea in simulation, running only a single job , deferring further discussion of this idea to future work. Hence, to compare against this approach, we are forced to construct our own working implementation of Pollux with goodput-based autoscaling (see Section 6 for details on our implementation of Pollux with autoscaling). 3. Theoretical Model and Results We model the GPU rental problem from the perspective of a customer who submits a stream of ML training jobs to be run in the cloud. Crucially, our model makes extremely general distributional assumptions about the various stochastic quantities in the system, meaning the results we derive can applied to a wide range of real-world systems. We model the case where the customer rents a single type of GPU, however our theoretical results generalize to the setting of heterogeneous GPUs (see Appendix E ). Due to space and cost constraints, we defer a full evaluation of BOA Constrictor on a heterogeneous cluster to future work. 3.1. Theoretical Model Training Jobs. Each training job has an associated job size that is defined as the amount of training progress that must be made for the model to reach a desired level of accuracy. In practice, we measure job size as a training job’s run time on a single GPU. We assume the customer has M different types (classes) of training jobs, each corresponding to a different combination of model and training data source. Let X_{i} be a random variable denoting the size of a type- i job. We assume that type- i jobs follow the same size distribution, but do not assume job sizes are independent from one another. A training job’s parallelizability is characterized by a speedup function, which indicates how the speed of processing a job varies as a function of the number of GPUs allocated to the job. We note that the speedup function of a training job can vary slowly with time as the training progresses. To capture this slow variation with time, we divide each type- i job into \ell_{i} statistical epochs ( qiao2021pollux ) . Each epoch j\in\{1,2,...,\ell_{i}\} has an associated random size X_{ij} and a speedup function s_{ij} which implies that if, in epoch j , the job is run on k GPUs, then the epoch will complete in time \frac{X_{ij}}{s_{ij}(k)} . Hence, a job’s total size satisfies X_{i}=\sum_{j=1}^{\ell_{i}}X_{ij} . To avoid the need of an integer programming formulation, we assume that the number of GPUs allocated to a job can be fractional. As prior work such as ( 10.1145/3641512.3686370 ) has shown, for large systems, fractional allocations can be converted into integral allocations using policies such as randomized rounding without any significant loss of efficiency. Arrival process and job size distribution. We assume type- i jobs arrive to the system with some long-run average rate \lambda_{i} . We assume that the j th epoch of each arriving type- i has a long-run average job size \mathbb{E}[X_{ij}] . We assume only that the long-run arrival rate and time-average job sizes above converge to the finite mean values above with probability 1, and that these means are known to the customer. We make no additional distributional or independence assumptions. In particular, the customer does not need to know the distribution X_{ij} , just its mean. We define the system load contributed by type- i jobs to be \rho_{i}=\lambda_{i}\mathbb{E}[X_{i}] . Intuitively, this \rho_{i} represents the long-run average number of GPU-hours required by the stream of type- i jobs when each job runs on a single GPU. It is also helpful to describe the load contributed by individual job epochs. We define \rho_{ij}=\lambda_{i}\mathbb{E}[X_{ij}] to be the load contributed by the j th epoch of the i th job type. Rescaling. Rescaling the number of GPUs allocated to a job will incur various overheads. This includes the time required to checkpoint a job’s progress, set up the runtime environment, the time needed to download job-specific container images and training data, and the time needed to restore a training job from a checkpoint on its new GPUs (see Section 5 for details). For simplicity, we begin Section 4 by considering the GPU rental problem without the above overheads, deriving the BOA policy in this simplified case. Then, in Section 4.3 , we will show how to generalize our model to account for rescaling costs, and how to optimize our BOA policy to achieve a low average JCT when rescaling costs are present. Much like the other stochastic quantities in our model, we model rescaling time as an unknown stochastic quantity that follows an arbitrary distribution. We assume only that a sequence of rescaling times will converge to some finite long-run average. The cost-performance tradeoff. Our goal is to design allocation policies that optimize the tradeoff between cost and performance by renting GPUs and allocating them to jobs over time. In terms of performance, this paper focuses on reducing Job Completion Time (JCT), the time from when a job arrives until it completes. We primarily consider minimizing the average JCT across a stream of arriving jobs. Let T_{i} denote the JCT of a class- i job, and let \mathbb{E}[T_{i}] denote its average. Our theory results also apply to any weighted average JCT, where each job type is assigned a weight. These weights can be used to ensure fairness across classes or reflect the relative importance of different job types. Although we do not explicitly optimize for tail performance, empirically BOA Constrictor greatly improves the tradeoff between cost and P95 JCT as well (see Section 6 ). In terms of cost, we assume that a GPU can be rented for a constant cost per hour. Hence, without loss of generality, we measure the cost of a cluster over time in GPU-hours. To control costs, the customer sets a time-average operating budget of b GPU-hours that the allocation policy must obey. Formally, to measure the cost of deploying an allocation policy, \pi , let K_{\pi}(s) denote the number of GPUs rented at time s . We measure the time-average cost of using the policy \pi as \displaystyle\mbox{Time-average cost }=\overline{K}_{\pi}=\lim_{t\to\infty}\frac{\int_{0}^{t}K_{\pi}(s)ds}{t}. We restrict our analysis to rental policies such that \overline{K}_{\pi} exists. The customer’s goal is to find a policy, \pi , that minimizes average JCT (or average weighted JCT) subject to the constraint that \overline{K}_{\pi}\leq b . 3.2. Modeling Assumptions We now state all assumptions needed for our theoretical results. Finite means: For the stochastic quantities in the system: interarrival times, job sizes, and rescaling times, we assume that the time averages for sequences of each quantity converge to some finite mean with probability 1. We make no other distributional assumptions. Notably, we allow correlations between job sizes and interarrival times, allowing us to model bursty, non-stationary workloads. Assumptions on speedup functions: We make mild assumptions on the form of the speedup functions. For any job type i , epoch j , s_{ij}(k) should fulfill the following properties: (1) s_{ij}(k) is defined on k\in[1,+\infty) and is continuous; (2) Monotonicity : s_{ij}(k_{1})\leq s_{ij}(k_{2}) for any 1\leq k_{1}0. Thus the optimization problem ( 6 ) is a convex optimization, which we can numerically solve for the optimal z_{ij} . Finally, given the optimal z_{ij} , we can get the optimal k_{ij} by letting k_{ij}=\beta_{ij}(\frac{1}{z_{ij}}) . ∎ Appendix C Detailed BOA width calculator We provide the detailed pseudocode for our BOA width calculator as follows. 1 Input: Total budget b , Job classes 1,\dots,M with epoch counts l_{1},\dots,l_{M} . Output: Optimal parameters \{k_{ij}^{*}\} for the fixed-width policy. 2 // First Step: Generate a set of glue configurations. \mathcal{G}\leftarrow\emptyset 3 for n\leftarrow 1 to 50 do 4 foreach job class i\in\{1,\dots,M\} do 5 Define candidate set S_{i}=\{2^{0},2^{1},\dots,2^{\lfloor\log_{2}l_{i}\rfloor}\} 6 Sample g_{i} uniformly from S_{i} 7 end foreach 8 Add configuration G=\{g_{1},\dots,g_{M}\} to \mathcal{G} 9 end for 10 11 // Second Step: Solve a feasible solution for each glue configuration. \mathbb{E}[T]_{\min}\leftarrow\infty 12 \{k_{ij}^{*}\}\leftarrow\emptyset 13 foreach G\in\mathcal{G} do 14 Construct super-epochs by gluing adjacent epochs for each class i according to g_{i}\in G 15 b_{run}\leftarrow b 16 b^{\prime}\leftarrow\infty 17 18 while b^{\prime}>b do 19 Compute \{k_{ij}\} by solving Optimization Problem ( 1 ) with budget b_{run} 20 Round each k_{ij} to the nearest integer on the non-decreasing concave hull of s_{ij} 21 22 Compute \mathbb{E}[T] and total cost b^{\prime} using \{k_{ij}\} (Lemma 4.8 ) 23 24 if b^{\prime}>b then 25 b_{run}\leftarrow 0.99\cdot b_{run} 26 else 27 if \mathbb{E}[T]<\mathbb{E}[T]_{\min} then 28 \mathbb{E}[T]_{\min}\leftarrow\mathbb{E}[T] 29 \{k_{ij}^{*}\}\leftarrow\{k_{ij}\} 30 end if 31 end if 32 end while 33 end foreach 34 35 return \{k_{ij}^{*}\} 36 Algorithm 1 BOA Width Calculator Appendix D Usage Statistics As discussed in Section 6.1 , the operating budget reported in Figure 4(a) reflects the effective GPU hours—the duration during which GPUs are actively allocated to jobs. This metric excludes the platform-dependent latency between when a node is marked for release by the allocator and when it is actually reclaimed by the cloud platform. Figure 11 extends Figure 4(a) by providing a comparison of the total usage for both policies. These results demonstrate that these infrastructure-level reclamation overheads affect the operating budget of both policies, but the negative effect on BOA Constrictor is smaller. Moreover, even with these infrastructure-level reclamation overheads, BOA Constrictor still significantly improves the Pareto frontier of average JCT vs. operating budget. Figure 11 . Actual Usage v.s. Effective Usage Appendix E Extension to heterogeneous servers While the core of BOA Constrictor is derived for a homogeneous cluster, our theoretical results (Section 4 ) generalize to settings with heterogeneous GPUs. We discuss the main idea in this appendix without rigorous proofs. In many cloud environments, customers can choose from various GPU types h\in H , each with distinct performance characteristics and rental costs. Here, similar to prior work ( subramanya2023sia ) , we focus on the case that the ML training jobs can run on any number of GPUs of any type (which results in different speed), but they cannot be run on different types of GPUs simultaneously. E.1. Model with heterogeneous servers For each job of class i at epoch j , its speedup function running on type h GPUs is denoted by s_{ij}^{(h)}(k) . In other words, if a class- i job in epoch j is run on k GPUs of type h , the epoch completes in time X_{ij}/s_{ij}^{(h)}(k) . Notably, s_{ij}^{(h)}(1) is not necessarily normalized to 1, representing the varying processing speed across hardware. Different GPUs have different rental price per hour. Let c^{(h)} denote the cost per hour for renting a single GPU of type h . The customer sets a time-average monetary operating budget b that the policy must obey. We maintain the assumptions that s_{ij}^{(h)}(k) is non-decreasing and concave for all h . E.2. Structural Properties and Variables In the heterogeneous setting without rescaling overheads, the following properties still hold: • No Queueing: The optimal policy does not queue jobs; every job is assigned to a server immediately upon arrival or epoch change. • Type-Specific Fixed-Width: For a specific server type h , all jobs of the same class and epoch should be assigned the same number of type h GPUs, k_{ij}^{(h)} . Note that a job can only be assigned to one type at a time. Thus, we are able to introduce the assignment fraction p_{ij}^{(h)}\in[0,1] , representing the fraction of jobs of class i at epoch j assigned to type h GPUs ( \sum_{h\in H}p_{ij}^{(h)}=1 for all i,j ). E.3. Heterogeneous BOA Optimization Problem The goal is to minimize the average JCT subject to the monetary budget constraint b . The optimization problem for the set of parameters \{k_{ij}^{(h)}\} and \{p_{ij}^{(h)}\} is: (7) \displaystyle\underset{k_{ij}^{(h)},p_{ij}^{(h)}}{\text{minimize}} \displaystyle\sum_{i,j,h}\frac{p_{ij}^{(h)}\rho_{ij}}{s_{ij}^{(h)}(k_{ij}^{(h)})} \displaystyle\text{subject to} \displaystyle\sum_{i,j,h}\frac{c^{(h)}p_{ij}^{(h)}\rho_{ij}k_{ij}^{(h)}}{s_{ij}^{(h)}(k_{ij}^{(h)})}\leq b \displaystyle\sum_{h\in H}p_{ij}^{(h)}=1,\quad\forall i,j \displaystyle k_{ij}^{(h)}\geq 1,\quad p_{ij}^{(h)}\in[0,1] Here, \rho_{ij}=\lambda_{i}\mathbb{E}[X_{ij}] is the load contributed by epoch j of type- i jobs. The budget constraint now captures the weighted sum of GPU-hours across different machine types, where each type h is weighted by its specific cost c^{(h)} . This remains a convex optimization problem through a change of variables similar to the one presented in Appendix B .