{"id":"aa9b7ae9-1299-4055-bc1e-cfa135ff0fc9","arxiv_id":"2412.09840","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"Repeatedly repredicting VM lifetimes and reclassifying hosts when predictions are wrong improves cloud scheduling efficiency over one-shot lifetime prediction.","lead":"Google engineers added lifetime predictions to VM scheduling, then updated those predictions as VMs run longer than expected. In production, this increased empty hosts by up to 9.2 percentage points and reduced stranded compute and memory by about 3% and 2%.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof in Appendix E has a reversed inequality and assumes oracle class revelation, so the 'fundamental advance' claim is not established.","rationale":"The reader's conditional verdict already flags the idealized ground-truth assumption, and I agree with that concern. An independent reading of Appendix E finds a stronger internal problem: the no-learning lower-bound inequality is reversed, so the proof as written cannot establish Theorem 1. This matters because the abstract's headline 'fundamental advance' is exactly the Ω(m) separation. The production measurements (2.3–9.2 pp empty hosts, ~3% CPU stranding, ~2% memory stranding, 4.5% migration reduction) and high-fidelity simulations are credible empirical support, and I do not dispute them; they justify an applied-systems contribution. But those measurements are A/B and CausalImpact analyses on a live system, not a controlled test of the asymptotic claim. The right disposition is the same CONDITIONAL verdict: either provide a correct proof under the actual LAVA update rule, or state the theorem more modestly and remove or soften the 'fundamental advance' wording. No change to the reader's verdict is needed.","tokens_in":23689,"tokens_out":9483,"duration_ms":99057,"concrete_test":"Independently re-derive the Appendix E probability bound: show that for x ≤ 1/(ϵρλ), Pr[V] ≤ 1−(1−ϵ)^(1/ϵ), not ≥, and check whether any Ω(m) host-count separation survives the corrected inequality and the production E(Tr|Tu) update rule. If no corrected derivation yields the bound, revise the theorem to match LAVA's actual deadline-based reclassification or remove the 'fundamental advance' claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 4.1's Theorem 1 is the only formal support for the abstract's 'fundamental advance' claim, and the proof in Appendix E is not sound. In the no-learning case the text asserts that for x ≤ 1/(ϵρλ), Pr[V] ≥ 1−(1−ϵ)^(ρλx). Since Pr[V]=1−(1−ϵ)^N is increasing in N=ρλx, the condition x ≤ 1/(ϵρλ) yields N ≤ 1/ϵ and therefore Pr[V] ≤ 1−(1−ϵ)^(1/ϵ). The claimed lower bound of 1−1/e is actually an upper bound, and the supporting bound (1−1/z)^z ≥ 1/e is also false for finite z>1. Thus the argument that mispredictions accumulate within a fixed interval does not go through. Separately, the learning model assumes that after S units the true short/long class is revealed; the production model only provides E(Tr|Tu), a noisy conditional expectation. So Theorem 1 neither follows from its assumptions nor describes LAVA's deployed mechanism. The production A/B and CausalImpact results remain credible empirical evidence for the practical improvements, but they do not by themselves establish the asymptotic separation claimed in the headline.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents LAVA, a lifetime-aware VM scheduling system for Google's Borg infrastructure. It predicts VM lifetime distributions, repredicts remaining lifetimes conditional on uptime, and uses three scheduling algorithms (NILAS, LAVA, and LARS) to improve bin packing, reduce resource stranding, and reduce live migrations. Production A/B tests and whole-pool CausalImpact analyses report empty-host increases of 2.3-9.2 percentage points, CPU stranding reductions of about 3%, memory stranding reductions of about 2%, and a 4.5% reduction in VM migrations; simulation studies on 24 C2 pools compare favorably with the LA-Binary baseline. The paper also claims a theoretical result (Theorem 1, Appendix E) that repredictions give an Omega(m) asymptotic advantage over one-shot prediction in the number of hosts required. That theoretical claim is the focus of the major concerns below.","tokens_in":23962,"tokens_out":6917,"duration_ms":70541,"significance":"The production-scale evaluation is the main strength of this paper: the A/B pilots, whole-pool CausalImpact analyses, and a simulator validated against production traces provide credible evidence that NILAS improves empty hosts and reduces stranding in a real hyperscale cloud. The comparison with a faithful implementation of LA-Binary in simulation, including oracle-lifetime runs, is a useful contribution. However, the theoretical 'fundamental advance' claim is not currently supported: Theorem 1's proof contains a reversed inequality and relies on an oracle-revelation assumption that the deployed conditional-expectation model does not satisfy. The practical contribution is significant, but the theoretical component needs major revision or a carefully limited restatement.","major_comments":[{"comment":"The proof of Theorem 1 does not establish the claimed lower bound. With N = rho*lambda*x, the event probability is Pr[V] = 1 - (1 - epsilon)^N, which is an increasing function of N. The condition x <= 1/(epsilon*rho*lambda) gives N <= 1/epsilon, so Pr[V] <= 1 - (1 - epsilon)^(1/epsilon), not the displayed '>='. The supporting inequality (1 - 1/z)^z >= 1/e is also false for finite z > 1; the correct direction is '<='. The later steps ('we will need to have cm misclassified jobs', 'we can now tolerate cm errors', and the Chernoff application) are asserted without derivations or parameter specification. Since Section 4.1 and the abstract's 'fundamental advance' claim rest on this theorem, the asymptotic separation must either be proven correctly or the claim must be substantially weakened.","section":"Appendix E, Theorem 1 and Eq. (1)"},{"comment":"Even if the probabilistic argument in Appendix E were repaired, Theorem 1 models a setting in which, after a job has run for S units, the scheduler learns the true short/long class. The production model of Section 3 only predicts E(Tr | Tu), a conditional expected remaining lifetime that retains prediction uncertainty; it never reveals the ground-truth class. Thus Theorem 1 is not a model of LAVA's deployed reprediction mechanism. The observed production and simulation gains may still be valid, but they are not consequences of this theorem. The paper should either prove the separation for noisy conditional expectations or explicitly limit the theoretical claim to the simplified oracle-revelation model.","section":"Appendix E; Section 3"}],"minor_comments":[{"comment":"The abstract states that 'our approach runs in production,' but Section 7 reports fleet-wide deployment only for NILAS; LAVA and LARS are validated in simulation. Please clarify the production scope to avoid overclaiming deployment of all three algorithms.","section":"Abstract; Section 7"},{"comment":"The 'host exit time' is defined as the maximum of the repredicted remaining VM lifetimes on the host, but Figure 4 labels it as an absolute exit time (e.g., 10h). Please clarify the convention (current time plus remaining lifetime) so that temporal cost computations are unambiguous.","section":"Section 4.2 and Figure 4"},{"comment":"The phrase '12.5%, 25%, ... of the original lifetime' should specify the exact set of uptime fractions used to augment training examples, since this determines the training distribution and the behavior of the conditional model.","section":"Section 3"},{"comment":"The first column 'Migrations Scheduled' is not used in the comparison, and the reduction percentage is relative to the Baseline column. Please annotate the table so the comparison is unambiguous.","section":"Table 2"},{"comment":"The caption says the figure shows 'relative improvements from LA-Binary,' but the axes are not labeled. Please add axis labels and explain what the correlation plot displays.","section":"Appendix D, Figure 13"}],"recommendation":"major_revision","confidential_remarks":"The production empirical evidence is credible and potentially publishable; the main risk is the unsupported theoretical claim in Theorem 1. If the authors can repair the proof, replace the oracle-revelation assumption with the actual conditional-expectation model, or appropriately weaken the 'fundamental advance' claim, I would be willing to support acceptance. Please also ensure the production-scope statements distinguish NILAS from LAVA and LARS."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Martin, here's my take on the LAVA paper. The production story is real and worth your time: they deploy lifetime reprediction for VM scheduling at Google, report empty-host gains of 2.3–9.2 pp, CPU and memory stranding reductions around 3% and 2%, and a 4.5% cut in migrations. They do this with three algorithms—NILAS, LAVA, LARS—and they compare against a faithful implementation of LA-Binary. The A/B experiments and CausalImpact analyses are credible, and the simulator validation is a nice touch. The fact that NILAS has been running fleet-wide for a year adds weight.\n\nWhat's genuinely new is applying LLAMA's reprediction idea to multi-dimensional VM scheduling and designing algorithms that actively correct mispredictions—especially LAVA, which does the opposite of LA by putting short-lived VMs on long-lived hosts to avoid extending host lifetimes. That's a real design insight.\n\nNow the soft spots. The main one is Theorem 1. The proof in Appendix E doesn't work: the inequality direction is reversed, and the bound (1−1/z)^z ≥ 1/e is false. More importantly, the proof assumes that after S units the true short/long class is revealed, but the production model only provides E(Tr|Tu), a noisy conditional expectation. So the 'fundamental advance' claim is not established by the theory. That's a load-bearing overclaim, though not a fatal one—the empirical results stand on their own. The authors should either fix the proof or tone down the headline.\n\nTwo smaller issues: the comparison omits DPBFR, which is what Barbalho et al. actually deployed; and simulation results lack error bars. No code or data is released, which is normal for production systems but limits reproducibility. The self-citation to LLAMA is fair—it's the same research line and clearly acknowledged.\n\nBottom line: this is a serious systems paper with credible production evidence. It deserves a regular review, not a desk reject. The theory needs to be repaired or removed, and I'd ask for the DPBFR baseline plus uncertainty estimates. If those land, I'd be happy to see it accepted.","headline":"Credible production evidence for reprediction-based VM scheduling, but the 'fundamental advance' theorem doesn't prove what it claims; still deserves a serious review.","tokens_in":24532,"tokens_out":2700,"would_cite":true,"duration_ms":26328,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Repredicting VM lifetimes beats one-shot prediction for cloud scheduling","keywords":["VM scheduling","lifetime prediction","reprediction","cloud data centers","survival analysis","bin packing","resource stranding","empty hosts"],"falsifier":"Run the paper's simulation on the same production traces with a one-shot predictor that is given every VM's true lifetime at creation time, and compare empty-host percentages to NILAS with repredictions; if the one-shot oracle matches or beats NILAS, the claimed $\\Omega(m)$ advantage of reprediction would be contradicted.","tokens_in":23484,"feed_emoji":"☁️","tokens_out":7680,"duration_ms":73260,"temperature":0.7,"pith_summary":"The paper argues that a cloud VM scheduler should not trust a single lifetime prediction made when a VM is created. Instead, it should repeatedly repredict remaining lifetimes from learned lifetime distributions, and adapt its placement decisions when earlier predictions turn out wrong. The authors claim this reprediction strategy is fundamentally more effective than one-shot prediction, backing the claim with a proof that a best-fit scheduler without reprediction needs $\\Omega(m)$ more hosts than the same scheduler with reprediction when initial prediction errors are a positive constant, and with a fleet-wide production deployment that increased empty hosts by 2.3-9.2 percentage points, reduced CPU and memory stranding by about 3% and 2%, and cut VM migrations by 4.5%.","feed_headline":"Repredicting VM lifetimes beats one-shot cloud scheduling","feed_subtitle":"A proof and production data show on-the-fly lifetime updates save hosts and cut migrations.","key_machinery":"The load-bearing mechanism is the lifetime distribution model combined with reprediction. A gradient-boosted decision tree is trained to output the conditional expected remaining lifetime given uptime, $E(T_r \\mid T_u)$, which turns a regression model into a survival model by injecting uptime as a feature. At scheduling time and during each VM's life, the scheduler draws updated exit times from this model and detects mispredictions such as hosts that should have emptied but have not. NILAS quantizes the temporal cost $\\Delta T = \\max(\\text{predicted VM exit} - \\text{host exit}, 0)$ into buckets as a tie-breaker in the scoring function; LAVA places hosts in open or recycling states across lifetime classes (LC1--LC4) and promotes or demotes a host's class when residual VMs exit or overstay; LARS migrates longest-lived VMs first during defragmentation. The supporting theorem compares a best-fit algorithm with and without learning in a two-lifetime model and shows an $\\Omega(m)$ gap in hosts required.","core_discovery":"The paper's central claim is that repredicting VM and host lifetimes, and actively responding to mispredictions, delivers a fundamental advance over one-shot lifetime prediction for VM scheduling. The authors introduce LAVA (Lifetime Aware VM Allocation), which models VM lifetimes as probability distributions and uses the conditional expected remaining lifetime $E(T_r \\mid T_u)$ to update each VM's exit time as it runs. Three scheduling algorithms exploit these updated lifetimes: NILAS adds a quantized temporal-cost score to an existing scheduler, LAVA deliberately places short-lived VMs on hosts with long-lived VMs so that host lifetimes are not extended, and LARS orders live migrations during defragmentation by remaining lifetime to reduce disruptions. The paper also proves that with constant positive initial prediction error, a best-fit scheduler that repredicts requires asymptotically fewer hosts, by $\\Omega(m)$, than the same scheduler that does not. Production measurements and high-fidelity simulations on production traces are presented as confirmation that the theoretical advantage appears in practice.","pith_inferences":["The theorem's idealized assumptions (two lifetime classes, constant arrival rate, ground truth revealed after $S$ time units) likely bound the real-world advance; production gains are finite and vary across pools, as the paper itself reports occasional inversions.","The reprediction principle transfers beyond VM scheduling to any allocation problem with heterogeneous object lifetimes, such as container orchestration, storage tiering, or resource management in serverless computing.","The paper's comparison uses a two-hour cutoff for the LA baseline; an evaluation against the production-deployed DPBFR variant of LA might show a smaller gap, since DPBFR is already designed for misprediction tolerance.","Because the production model only supplies a noisy conditional expectation, the asymptotic $\\Omega(m)$ advantage should be tested empirically across pools with different prediction accuracies rather than taken as a guaranteed rate."],"forward_implications":["Reprediction makes lifetime-aware scheduling robust to imperfect predictions, so the approach remains effective when the ML model degrades or encounters unfamiliar workloads.","More empty hosts directly increase the capacity available for large VMs, speed up maintenance rollouts, and reduce idle power consumption.","Reducing CPU and memory stranding recovers roughly 2-3% of cluster capacity, which the paper equates to about 1% of a cluster's capacity per percentage point.","LARS's lifetime-ordered migration reduces live migrations by about 4.5%, cutting disruption during defragmentation and maintenance.","With oracle lifetimes and ideal placement, NILAS approaches the theoretical maximum of empty hosts, indicating the greedy reprediction policy is close to optimal."],"supporting_citations":[{"why":"Defines the prior state-of-the-art Lifetime Alignment (LA) algorithm and the LA-Binary baseline that the paper must outperform; its reported sensitivity to mispredictions motivates reprediction.","marker":"Barbalho et al., 2023"},{"why":"Supplies the core idea of repredicting and correcting mispredictions in lifetime-based allocation (the LLAMA memory allocator), which the paper transfers to VM scheduling.","marker":"Maas et al., 2020"},{"why":"The CausalImpact Bayesian structural time-series method used to estimate the production effect of NILAS on empty hosts and stranding.","marker":"Brodersen et al., 2015"},{"why":"Describes the Borg cluster manager in which NILAS, LAVA, and LARS are integrated and whose scoring function they extend.","marker":"Verma et al., 2015"},{"why":"Survey of survival analysis that grounds the paper's use of lifetime distributions and conditional remaining lifetimes.","marker":"Wang et al., 2019"},{"why":"Nonparametric survival estimator used as a baseline model and as the conceptual basis for lifetime distributions.","marker":"Kaplan & Meier, 1958"}],"fun_headline_variants":["Repredicting VM lifetimes beats one-shot scheduling","LAVA repredicts VM lifetimes to free up hosts faster","Cloud repredictions cut stranded resources by 3%","VM repredictions slash migrations and energy waste"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that after a job has run for a short fixed time $S$, the scheduler learns the job's true lifetime class, but in production the scheduler only receives a noisy predicted remaining lifetime, so the proof's clean 'learning after $S$' step is stronger than what the deployed system actually provides.","fun_headline_variants_meta":{"raw":{"variants":["Repredicting VM lifetimes beats one-shot scheduling","LAVA repredicts VM lifetimes to free up hosts faster","Cloud repredictions cut stranded resources by 3%","VM repredictions slash migrations and energy waste"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000234,"raw_usage":{"total_tokens":1530,"prompt_tokens":1014,"completion_tokens":516,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":630,"completion_tokens_details":{"reasoning_tokens":452}},"tokens_in":630,"tokens_out":516,"duration_ms":6366,"temperature":1.0,"reasoning_tokens":452,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T16:39:27.252195+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the paper's simulation on the same production traces with a one-shot predictor that is given every VM's true lifetime at creation time, and compare empty-host percentages to NILAS with repredictions; if the one-shot oracle matches or beats NILAS, the claimed $\\Omega(m)$ advantage of reprediction would be contradicted.","supporting_citations":[{"cited_title":"R., Dion, D., Moscibroda, T., and Menache, I","cited_arxiv_id":null,"evidence_quote":"Defines the prior state-of-the-art Lifetime Alignment (LA) algorithm and the LA-Binary baseline that the paper must outperform; its reported sensitivity to mispredictions motivates reprediction."},{"cited_title":"H., Gallusser, F., Koehler, J., Remy, N., and Scott, S","cited_arxiv_id":null,"evidence_quote":"The CausalImpact Bayesian structural time-series method used to estimate the production effect of NILAS on empty hosts and stranding."},{"cited_title":"R., Oppenheimer, D., Tune, E., and Wilkes, J","cited_arxiv_id":null,"evidence_quote":"Describes the Borg cluster manager in which NILAS, LAVA, and LARS are integrated and whose scoring function they extend."}],"review_version":1}