Cloud operators sell more capacity than they own. This is called overbooking, and it is safe only because tenants rarely peak at the same moment, so their combined demand is smoother than any one tenant's. That safety disappears when tenants are correlated, for example through a shared diurnal cycle or a flash crowd hitting several services at once. The chance that a host overflows depends on the variance of the sum of its tenants' demands, and that variance requires every pairwise covariance among the tenants placed together. Across a fleet with many tenants, that is a quadratic number of quantities, and the placement search has to evaluate it for colocation sets that have never existed together.
We propose to model fleet demand covariance as low-rank plus diagonal. Each tenant loads on a few shared "demand factors" and also has its own independent noise. Under this model a host's risk becomes additive: the host's variance is the squared length of the summed factor loadings plus the summed individual variances. Placement then turns into vector packing in a small factor space. The placer can deliberately separate tenants that load on the same factor, and it can admit more load wherever factors cancel. The question we want to answer is whether this correlation-aware placement packs hosts more densely at a fixed overflow rate than either independence-based overbooking or reactive headroom.
Core Claim
Two moments of the per-host sum are enough to bound overflow risk without assuming any distribution. If host $h$ has aggregate demand mean $\mu_h$, variance $\sigma_h^2$, and capacity $C$, the one-sided Chebyshev (Cantelli) inequality gives
$$P(S_h > C) \le \frac{\sigma_h^2}{\sigma_h^2 + (C-\mu_h)^2}.$$
This bound is distribution-free, which matters for the heavy-tailed traces described below. It also shows that covariance is the only hard part of the problem. Suppose demand covariance is $\Sigma = D + UU^\top$, where $D$ is diagonal, the loading matrix $U$ is $M \times k$, $M$ is the number of tenants, and $k \ll M$ is the number of factors. Then
$$\sigma_h^2 = \sum_{i \in h} D_{ii} + \Big\| \sum_{i \in h} u_i \Big\|^2,$$
where $u_i$ is row $i$ of $U$. Each candidate move costs $O(k)$ to evaluate instead of $O(|h|^2)$. Tenants whose loadings point in opposite directions reduce the host's risk.
The new elements are three. First, we treat placement as packing in loading space rather than scalar packing. Second, we fit the low-rank part with a diagonal correction so that each tenant's own variance is exact while correlations are captured approximately. Third, we inflate the factor-space norm by the estimation error in the loadings. This last step gives a pessimistic risk bound for tenants with little history.
Relation to Prior Work
The motivation comes from online serverless placement. Online Learning for Function Placement in Serverless Computing places functions using KL-UCB bandit indices inside a linear program. It is optimistic about costs and pessimistic about resource use, and it rejects excess load through a fictitious node. The authors state that it assumes i.i.d. demands and name correlated demands as future work. We keep their "safety first" pessimism but apply it to correlated host sums rather than to independent per-function means.
Resource Management in Aurora Serverless shows production overbooking that is deliberately reactive: token-bucket growth limits plus live migration. It keeps the fleet unbalanced so that lightly loaded hosts are always available as migration targets. Our method is an attempt to price that headroom explicitly instead of holding it blindly.
Overbooking with Bounded Loss proves horizon-independent loss for a critical-ratio index policy in a single-resource setting with known distributions. It leaves multi-resource networks open. Our setting is both multi-host and learned online, so we use its index only as an admission baseline.
The method itself is borrowed from the covariance-scaling literature. Estimating Model Uncertainty of Neural Networks in Sparse Information Form uses spectral sparsity: it applies a low-rank approximation to the information matrix of a network and adds a diagonal correction so that per-parameter variances stay exact. The paper reports that keeping 5% of ranks often beats full-rank KFAC. We transplant this "low rank plus exact diagonal" construction from parameter space to tenant-demand space. The motivating bet is that fleet demand, like network curvature, has a rapidly decaying spectrum. That bet must be checked empirically, not assumed.
The diagonal-collapse evidence from Learning Neural Contextual Bandits through Perturbed Rewards motivates why the off-diagonal terms matter. That paper reports a significant performance drop when only the covariance diagonal is used. A further note of caution comes from Farquhar et al., who argue that correlation modeling can be redundant when other structure supplies it. Our ablations test whether that is true here.
Research Program
We will build per-minute demand vectors for each tenant from the 14-day Azure Functions production trace characterized in Practical Scheduling for Real-World Serverless Computing. The demand for a function in a given minute is its invocation concurrency multiplied by its allocated memory. That paper reports heavy-tailed durations and extreme skew, with 0.6% of functions producing 90% of traffic. Lacuna lists no dataset artifact for this trace.
The estimator is fit on rolling windows using streaming truncated eigendecomposition of the residuals after removing per-tenant seasonal means. Its rank $k$ is chosen by held-out log-likelihood. For tenants with short histories, we place a confidence ellipsoid around $u_i$ and inflate the host norm by its radius. This is the pessimistic step.
The placer has three parts. It uses greedy first-fit in loading space, it applies a local search that swaps tenants to reduce $\|\sum u_i\|$, and it admits a tenant only if the Cantelli bound stays below a target $\epsilon$. We will also embed the per-host risk constraint into the linear program of the Combes et al. testbed, replacing its independent resource bounds. We will extend that testbed, which uses up to 100 nodes and 10 classes with Bernoulli and uniform demands, by adding injected common factors with controlled strength. This gives a setting where the ground truth is known.
Baselines
The naive reference point is peak reservation, which never overbooks. It defines the packing floor and gives zero overflow.
The independence baseline is the closest published method. It is the pessimistic per-function bound of Online Learning for Function Placement in Serverless Computing, run in its own simulator and on the Azure-derived demands with the same $\epsilon$. That paper reports that constraints stay below the 1.0 threshold during learning, with near-optimal convergence within 300 seconds and decisions under 0.6 ms at 100 nodes. Those results hold only under i.i.d. demand. Beating this baseline means achieving equal or higher packing density while its measured overflow exceeds $\epsilon$ in correlated windows and ours does not.
The reactive baseline is a reimplementation of the Aurora policy, with token-bucket growth and a reserved fraction of migration-target hosts. The paper reports 99.98% in-place scale-ups and 54.9% of provisioned ACU-hours, but those figures come from proprietary fleets. We therefore compare only in our own simulator: at matched throttled-minute rates, which method uses fewer hosts?
The strongest covariance competitor is the full empirical covariance with Ledoit-Wolf shrinkage, used inside the same Cantelli placer. It gets the same windows and the same tuning budget, with the shrinkage intensity and our rank $k$ each searched over equal grids.
Admission is additionally compared against the critical-ratio index of Overbooking with Bounded Loss.
Four ablations isolate the key ingredients. The first drops the diagonal correction. The second uses the factor model for admission only, without anti-colocation search. The third removes the epistemic inflation for new tenants. The fourth sets $k=0$, which reduces the method to independence with exact variances.
Why not just…?
Why not just assume independence with a safety margin? This is exactly the regime that Combes et al. flag as unhandled. Any fixed margin is either too tight during correlated bursts or wasteful the rest of the time. The $k=0$ ablation with a margin tuned on training windows will show whether a single margin generalizes to held-out days. We expect it to fail on days with diurnal shifts.
Why not just measure each host's aggregate history and keep headroom, as Aurora does? History exists only for colocation sets that have already occurred. Placement asks about sets that have never existed. Reactive headroom works, but it holds unpriced idle hosts. The reactive baseline comparison measures how much of that headroom the factor model can safely release.
Why not just use a full shrinkage covariance? This is a real threat when the number of tenants is in the hundreds, where an $M^2$ matrix is cheap. We will report results as a function of $M$, the per-move evaluation cost, and the held-out calibration. If shrinkage matches our method in both density and calibration at every scale we can reach, the contribution reduces to search speed, and we will say so.
Why not just use a neural contextual bandit such as NeuralUCB or NPR? Neural Contextual Bandits with UCB-based Exploration and NPR handle unconstrained per-decision reward. Neither represents the joint tail of a host's sum, which is the quantity that determines overflow. The two approaches could be combined later, with a network predicting loadings for new tenants, but that is not the first-order question.
Proposed Experiments
The first check concerns spectral structure. Does residual demand covariance on the Azure trace decay fast enough that a small $k$ explains most of the variance of host sums? If it does not, the premise fails.
The second check concerns calibration. Predicted overflow probabilities should match realized per-host-minute overflow on held-out days. We will evaluate this with reliability curves across $\epsilon \in \{10^{-2}, 10^{-3}\}$.
The decisive test is the density–overflow frontier. Hosts used, and the overbooking ratio of sold to physical capacity, are plotted against realized overflow for all baselines. In the synthetic testbed, we will vary factor strength so that the expected crossover becomes visible. Independence should be competitive at zero correlation and should violate $\epsilon$ as correlation grows. Lacuna reports no prior result for correlated placement on the Azure trace, so all numbers on that benchmark will be new.
References
- Online Learning for Function Placement in Serverless Computing
- Resource Management in Aurora Serverless
- Overbooking with Bounded Loss
- Estimating Model Uncertainty of Neural Networks in Sparse Information Form
- Learning Neural Contextual Bandits through Perturbed Rewards
- Liberty or Depth: Deep Bayesian Neural Nets Do Not Need Complex Weight Posterior Approximations
- Practical Scheduling for Real-World Serverless Computing
- Neural Contextual Bandits with UCB-based Exploration