CARA: Exact Local Repair with Fresh One-Action Certification for Cloud Consolidation Xiyang Zhang1,2 , Yuanhe Tian1∗ , Hongzhi Wang2 1
Zhongguancun Academy Harbin Institute of Technology [email protected], [email protected], [email protected] 2
arXiv:2607.29465v1 [cs.DC] 31 Jul 2026
Abstract Simulator-based placement pipelines may inspect many repairs but deploy only when several reliability criteria improve together. Reusing search scenes to test the selected action invalidates nominal evidence, while scalarization can trade away the weakest criterion. We introduce Certificate-Aligned Recomposition (CARA), an incumbent-anchored pipeline that separates adaptive proposal generation from a one-use deployment decision. In a bounded two-host neighborhood, a packing-specific admissible bound recovers the exact top-P distinct actions under a mixed paired-binary/fixed-bet certificate order. Held-out views then select one action and commit its betting plans before fresh paired Certification opens. Under the stated sign-independence and conditional-moment assumptions, the probability of falsely declaring four-way improvement is at most .05, irrespective of the size or complexity of upstream search. In a prospectively frozen study over 128 independent synthetic environments and four repeated contexts, the complete fail-closed terminal policy improved a development-selected same-host-count incumbent on all five Evaluation endpoints in every environment. J fell by 3.57 percentage points and the continuous burdens by 21–28%. A matched ordering sensitivity produced absolute mean gaps below 5.3 × 10−4 and does not establish order superiority. CARA thus couples exact auditable proposal recovery to selection-robust fresh certification for last-mile local repair.
Introduction Cloud placement is a packing problem whose inputs are forecasts rather than fixed demands. Production schedulers must balance several resources (Grandl et al. 2014), and statistical overcommitment makes overload risk a deployment concern rather than a feasibility afterthought (Cohen et al. 2019). Correlated demand further weakens decisions based only on per-item summaries (Luo et al. 2021). We study the last step of such a pipeline: a simulator can inspect many local repairs, but the operator deploys only when every monitored reliability burden improves. This setting creates the two failures in Figure 1. First, a weighted objective can purchase a large average gain by worsening the weakest reliability coordinate. Second, testing the winner on the scenes used to find it treats an adaptive choice as if it had been fixed in advance. Predict-then-optimize methods explicitly couple ∗
Corresponding author.
Figure 1: Two failures and CARA’s remedy. Scalarization can worsen the weakest burden, and reusing search scenes invalidates evidence. CARA aligns proposals with the certificate, commits one action, and certifies it on fresh paired scenes. predictions to downstream decisions (Elmachtoub and Grigas 2022), while decision-focused learning optimizes through that downstream objective (Wilder, Dilkina, and Tambe 2019; Mandi et al. 2024). Neither coupling by itself makes reused post-selection evidence valid. Classical sample splitting addresses this information leak by separating adaptive choice from inference (Cox 1975). Our target is deliberately narrower than global consolidation. The operator has already chosen a one-host reduction and constructed a deployable action at that host count. We ask whether a bounded two-host recomposition can improve that action on all monitored burdens and whether exactly one selected repair can be compared on untouched evidence. The upstream H0 → H0 − 1 decision remains outside the module’s contract; a failed repair retains the existing host saving. This incumbent-relative formulation matches the operational principle of high-confidence policy improvement, which also anchors a proposed policy to a known fallback (Thomas, Theocharous, and Ghavamzadeh 2015; Laroche, Trichelair, and Tachet des Combes 2019). Certificate-Aligned Recomposition (CARA) separates proposal fidelity, decision validity, and terminal utility. Search ranks bounded physical repairs by a fourcoordinate key formed from one projected paired-binary certificate and three projected fixed-bet certificates. Directed arithmetic places the coordinates on a common lattice, and a packing-specific admissible bound recovers
the exact top-P distinct actions. Held-out views reduce this set to one action and freeze its betting plans, endpoint definitions, and scene order. Only then does a fresh paired Certification bank open. Release requires all four components to pass; every veto, failed component, empty search, work cap, or unresolved arithmetic boundary returns the committed incumbent without retrying another candidate. The anchor itself is fixed without formal outcomes. A disjoint Development-B study evaluates five action generators, freezes a first choice and fallback order, and constructs a same-host-count incumbent in each formal cell. That action is durably committed before CARA Search and is both the comparison zero and the operational fallback. If the frozen roster cannot construct a verified H0 −1 action, both policies receive the structural H0 scaffold and an exact zero contrast. Thus the terminal analysis retains ordinary fallbacks, structural failures, and recovery paths rather than conditioning on successful search or release. Our contributions are as follows. • Exact certificate-aligned recovery. A packing-tree bound handles unknown descendant bets, outward rounding, leximin comparison, and action deduplication, returning the exact distinct top-P under the registered mixed order. • Selection-robust one-use certification. Held-out data commit one action and its plans before a fresh paired bank opens. Under the stated conditional paths, false four-way release is at most .05, regardless of search size. • Complete terminal evaluation. We evaluate the failclosed policy rather than only released actions, retaining every fallback, structural failure, and recovery in the terminal comparison. The prospectively frozen study contains 128 independently generated synthetic environments, four repeated contexts per environment, and all 512 resulting cells. Relative to the same-host-count incumbent, CARA passed the registered mean and sign gates on all five Evaluation endpoints. The binary burden J fell by 3.57 percentage points, the continuous burdens fell by 21–28%, and every environment-level difference favored CARA on every endpoint. A matched ProjBlind-2H sensitivity has slightly lower point estimates, so these data establish neither superiority nor equivalence between the two proposal orders. The durable result is instead the audited interface: exact local proposal recovery, one committed action, fresh certification, and complete terminal accounting.
Related Work Cloud consolidation under uncertain demand. Classical packing combines set-partitioning models, branching, and problem-specific bounds (Gilmore and Gomory 1961; Coffman, Garey, and Johnson 1996; Delorme, Iori, and Martello 2016). Multidimensional variants capture several resource types (Chekuri and Khanna 2004). Under uncertain demand, chance-constrained and scenario formulations seek placements that remain feasible with high probability (Song, Luedtke, and Küçükyavuz
2014; Zhang, Denton, and Xie 2020; Borges et al. 2024). Stochastic bin-packing formulations likewise optimize against a demand law rather than one deterministic load vector (Martinovic and Selch 2021). Cloud systems add statistical overcommitment (Cohen et al. 2019), correlation-aware placement (Luo et al. 2021), and workload-specific scheduling constraints (Roytman et al. 2013; Yan et al. 2022). These lines of work primarily ask how to construct a feasible or efficient placement under uncertainty. CARA starts after a host target and verified incumbent already exist. It neither changes the fitted demand model nor claims global packing optimality; it asks which bounded last-mile repair should be proposed and what fresh evidence is required before that repair may replace the incumbent. Ranked and multiobjective search. K-best enumeration returns an ordered prefix rather than one optimizer (Murty 1968; Lawler 1972). Multiobjective branch-andbound extends exact search to partially ordered criteria (Przybylski and Gandibleux 2017), and leximin prioritizes the weakest coordinate before progressively stronger ones (Bouveret and Lemaître 2009; Ogryczak 1997). ILS and adaptive large-neighborhood search offer heuristic alternatives when the neighborhood is too large for exhaustive enumeration (Lourenço, Martin, and Stützle 2003; Ropke and Pisinger 2006; Pisinger and Ropke 2019). Hybrid bin-packing heuristics and exact solvers provide complementary structural baselines (Alvim et al. 2004; Scholl, Klein, and Jürgens 1997). Most ranked-search results assume that the leaf objective is already evaluable and focus on enumerating the next solution. Here a descendant’s betting plan is not yet known, the score mixes binary and continuous certificate forms, and multiple seed–block origins can reach the same physical placement. Our exactness claim therefore concerns a specific optimistic bound, lattice order, and deduplicated action universe. It holds only when the registered work caps do not bind. Fidelity to this local order does not imply that the order is empirically superior to another proposal rule. Post-selection risk control. Data splitting separates adaptive selection from later inference (Cox 1975). Learn-then-Test controls risk over a finite configuration family (Angelopoulos et al. 2025); Pareto Testing estimates a multiobjective frontier on one split and orders and tests it on another (Laufer-Goldshtein et al. 2023). Conformal risk control instead calibrates expected monotone losses (Angelopoulos et al. 2024). These general selectthen-test patterns are prior art. Incumbent-relative safe policy improvement provides another relevant template, but focuses on off-policy evaluation in sequential decision processes (Thomas, Theocharous, and Ghavamzadeh 2015; Laroche, Trichelair, and Tachet des Combes 2019). CARA instead specializes the split pattern to paired placement scenes. It uses McNemar’s exact test for the binary component (McNemar 1947), fixed betting wealth for three bounded continuous components (Shafer et al. 2011; Ramdas et al. 2023), and an intersection–union decision for the conjunctive claim (Berger and Hsu 1996). The Q53 correction is deterministic quantization for the betting factors, not a conformal score. The resulting guar-
antee is conditional per committed action, rather than family-wise or conformal risk control. Its distinctive contract is to freeze one physical action and all of its plans, open fresh paired evidence exactly once, and fall back without testing a second winner.
Problem Setting For scene b, VM i, time t, let xbit ≥ 0 be load and Ct > 0 be capacity. Fit constructs a covariance-feasible structural placement π str with H0 hosts. Before CARA begins, the frozen comparator algorithm constructs and commits the deployment incumbent π I with exactly H0 − 1 nonempty hosts when its frozen generator roster succeeds. Every candidate π has the same host count. For any placement, let Db count hosts with an overload exceeding the fixed binary64 tolerance, Lb count violating host–time pairs, and P X [ i:π(i)=h xbit − Ct ]+ Eb (π) = . (1) Ct h,t
Using H0 as a common normalizer, define Jb (π) = 1{Db (π) > 0}, Vb (π) = Db (π)/H0 , Rb (π) = Lb (π)/(H0 T ), Sb (π) = min{Eb (π)/(κH0 T ), 1}. (2) Raw severity ub = Eb /(H0 T ) is retained for Evaluation. For raw severity, the e-Guard uses only the bounded proxy ψκ (u) = u/(u+κ); a claim about its mean does not imply one about the unbounded raw mean. The terminal policy deploys either a released recomposition or π I . If the frozen roster returns no verified H0 − 1 action within its registered contract, the intention-to-treat rule assigns the structural H0 action to both policies and an exact zero contrast rather than deleting the cell. Lower is better on every endpoint. Both actions therefore equal the precommitted cell target, either H0 − 1 or the structural H0 zero state. Host count is a construction check, not a sixth hypothesis, and no claim compares unlike host counts or asserts absolute SLA satisfaction. The experimental section defines the cluster-level confirmatory estimand and all-five decision rule.
Certificate-Aligned Recomposition Figure 2 separates the committed incumbent, adaptive proposal and held-out choice, and the fresh decision. Search consumes no Certification outcomes. One action and its plans are fixed before the fresh bank opens; failure returns π I without testing another winner.
A Committed Same-Host-Count Anchor Development-B contains ten environments crossed with the four registered contexts. In each of its 40 cells, five generators construct H0 − 1 actions from Fit and Build; a disjoint view scores those fixed actions. A registered scale-free rule first maximizes eligible cells and then full-leximin orders all endpoint midranks. Eligibility was 35/40 for Global96, 35/40 for ProjBlind-2H, 38/40 for verified evacuation, 4/40 for ILS, and 0/40 for ALNS.
The rule selected verified evacuation and froze the fallback order ProjBlind-2H, Global96, ILS, then ALNS before the formal study. In each formal cell, generators run in that order using Fit and Search/Plan only. The first nonempty verified set is reranked by the exact four-endpoint certificate key, and its best H0 − 1 action is durably committed before CARA Search. We therefore call π I the certificatereranked frozen-generator incumbent; retaining it keeps the same host count as every candidate. If no generator succeeds, the pre-Search commit instead fixes the structural H0 action for both policies and Search does not create an efficacy-bearing contrast. Let π (s) , s = 1, . . . , S, be verified H0 − 1 seeds constructed without later outcomes. For each unordered pair of nonempty seed hosts, take their item union U when 2 ≤ |U | ≤ m. Other hosts remain fixed while Search enumerates every nonempty bipartition of U into two replacement hosts. Canonical labels remove host symmetry; full structural and covariance replay removes invalid leaves. Equality of canonical physical assignments defines deduplication across seeds and blocks; a digest only indexes and audits that identity. The unchanged incumbent is explicitly excluded.
Exact Search on the Certificate Lattice Write nB and nC for Search/Plan and Certification sizes and assume r = nC /nB is an integer. For J, let A count candidate-only harmful Build discordances and B incumbent-only harmful discordances. The projected margin is Z ∼ Bin r(A + B), 1/2 , pJ (A, B) = Pr{Z ≤ rA},
θJ = log(.05) − log pJ . (3) Let M = 253 . For stored binary64 z ∈ [0, 1], let C53 (z) count indices k = 0, . . . , M − 1 satisfying (k+1/2)/M ≤ z; equivalently, C53 (z) = ⌊M z+1/2⌋ ∈ {0, . . . , M }. For e ∈ {V, R, S}, define dei = C53 (ei (π I )) − C53 (ei (π)), Xei = (dei − 1)/(M + 1).
(4)
Thus dei ∈ [−M, M ] and Xei ∈ [−1, (M −1)/(M +1)]. A Build-only fitter exhausts λ = j/256, j = 0, . . . , 255, under a specified binary64 log-sum, bucket, and tie rule. With the chosen λe , the target-size margin is θe = r
nB X
log(1 + λe Xei ) − log 20.
(5)
i=1
These projections rank Build actions; they are not future evidence or Certification p-values. Certificate-form alignment. For an action–plan pair, including λe , fixed before both Build and Certification panels, suppose their increments are i.i.d. from the same conditional row law. Put Ye = log(1 + λe Xe ), µe = EYe , and γe =Qµe − log 20/nC . For fresh CernC tification, let We = i=1 (1 + λe Xei ). The support is Ye ∈ [− log 256, log 2]. When γe > 0, Hoeffding’s in-
Figure 2: The CARA contract. A frozen generator commits the deployment incumbent before exact local Search. Held-out views fix one candidate; fresh Certification releases it once or returns the incumbent. Evaluation retains every fallback as an intention-to-treat outcome. equality gives Eθe = nC µe − log 20, Pr{We < 20} ≤ exp{−2nC γe2 /(log 512)2 }.
(6)
Thus each continuous projection targets the same loggrowth and threshold used by Certification. In CARA, however, the action and plan are chosen adaptively from Build; the realized projection is neither a post-selection unbiased estimate nor a lower confidence bound. It gives objective alignment, not guaranteed power or utility, which is why held-out selection and fresh Certification remain necessary. Exact recovery below is fidelity to this objective, not a claim that it dominates another proposal order. Directed arbitrary-precision intervals enclose each target margin. Precision increases until both endpoints occupy the same cell of a common 2−40 integer lattice; an unresolved boundary fails closed. A leaf key sorts its four labeled cells from weakest to strongest and compares these vectors lexicographically. Only a complete lattice tie reaches the canonical physical-assignment row. The key bound comes from the packing structure. At a partial node v, unassigned VMs are omitted. Since loads are nonnegative, completing the node can only increase candidate burdens relative to the fixed incumbent and hence cannot improve the projected McNemar margin. Moreover, for every descendant a and its fitted 0 ≤ λa ≤ 255/256, partial differences satisfy Xi (v) ≥ Xi (a) and 255 X θe (a) ≤ r max{Xi (v), 0} − log 20 =: θe (v). 256 i (7) This follows from log(1 + λX) ≤ λX ≤ (255/256) max{X, 0} and is independent of the descendant’s plan. Rounding the envelope outward onto the same lattice gives a labeled optimistic vector; sorting preserves componentwise dominance. Once P distinct leaves are
retained, Search prunes only a strict loss to the current P th vector. Equality is kept because the physical tie row is not known at an internal node.
Held-Out Choice and One-Use Certification Cover replays only the exact top-P set on its heldout Build half. Four identity-fixed folds turn each endpoint’s readiness into exact midranks and then each action’s weakest endpoint into qaf ∈ [0, 1]. With K = min{4, P }, Cover enumerates the small family Sb ∈
arg max ∅̸=S⊆[P ], |S|≤K
1 4
4 X f =1
max qaf . a∈S
(8)
This is the familiar monotone-coverage objective (Nemhauser, Wolsey, and Fisher 1978), but P ≤ 16 makes all at most 2,516 subsets enumerable. Route uses its disjoint Screen view to choose one member of Sb by a threshold-centered full-leximin ordinal. Neither stage refits the action’s plans. On the remaining Screen rows, a conservative rawdirection gate first maps each finite nonnegative binary64 raw severity to C53 (u) = ⌊253 u + 1/2⌋. It forwards the action only if X raw raw {C53 (ui (π I )) − C53 (ui (π)) − 1} ≥ 0. (9) i
The one-count correction makes this a conservative statement about the observed held-out raw mean; it is neither population inference nor a raw-safety certificate. The harm-only e-Guard then compares the routed action with π I on J, V, R, S and the bounded raw proxy ψκ (u). Each candidate-minus-incumbent increment feeds a fixed 255-point mixture of nonnegative betting products; a mixture value at least 100 vetoes. No alarm is only a handoff to Certification. The exact transform and its false-veto proposition appear in the supplement. That proposition conditions before the shared
Guard rows open and does not give a guarantee conditional on first passing the raw-direction gate. Unbounded raw severity remains in Evaluation to expose proxy misspecification, but no bounded-tail contract was prespecified; raw direction and proxy harm are screens, not a fifth Certification component. Before Certification outcomes are observed, the protocol fixes the routed action, π I , all three continuous plans, scene order, and endpoint definitions. On fresh common scenes, the J component applies the exact paired lowertail test, while each continuous component forms We =
nC Y
(1 + λe Xei ).
(10)
i=1
Release requires the McNemar component and all three events We ≥ 20. Any failed component, veto, empty search, cap, or unresolved boundary executes π I ; there is no retry. Evaluation opens only after every terminal action is immutable.
Theory Guarantees Theorem 1 (exact distinct-action top-P ). Let A(π I ) contain the distinct valid H0 − 1 actions obtained from every registered seed and eligible two-host block, excluding π I . Assume nonnegative loads, a complete canonical seed–block inventory, complete structural and covariance replay, and physical deduplication. If every arithmetic interval resolves and neither deterministic work cap is reached, strict-only branch-and-bound returns the first min{P, |A(π I )|} actions ordered by decreasing incumbent-relative full-leximin lattice vector and then by increasing canonical physical assignment. The proof uses nonnegative partial loads to obtain labeled optimistic margins. A plan-independent log-wealth envelope is rounded outward to the common lattice, and sorting preserves componentwise optimism. A strict loss to the current P th vector is therefore safe to prune; equality remains open until the physical tie row is known. Complete replay and canonical equality remove only invalid or duplicate actions. The supplement gives the traversal, admissibility, arithmetic, and O(SH 2 2m ) local-node arguments. This is an exactness result for the registered neighborhood and order, not a global packing guarantee or evidence that the order dominates another objective. For the statistical result, let H− contain the fixed environment parameters and the complete transcript through e-Guard: the incumbent, routed action, betting plans, earlier outcomes and decisions, scene order, and endpoint definitions, but no Certification innovations or endpoint values. Fresh Certification rows follow their registered law independently of this upstream transcript. Conditional on H− and the discordance set, the binary signs are independent and, under the binary null, are candidateharmful with probability at least one half. For each continuous endpoint, a true null follows either the registered conditional-supermartingale mean path or the registered conditionally independent average-mean path for the corrected Q53 increments. The supplement states sufficient conditions in the original burden scale. Theorem 2 (selection-robust one-use control). Under
these assumptions, if at least one of the four component nulls is true, Pr{release π | H− } ≤ .05.
(11)
The bound is unchanged by the number or complexity of actions considered before H− was fixed. The paired binary tail is super-uniform; each fixed-bet wealth has null expectation at most one, so Markov’s inequality limits its rejection probability to 1/20. Because release is an intersection–union event, no alpha split is required. Any upstream proposal and routing method may replace CARA Search without changing this result if it commits exactly one action and its plans before the fresh bank opens. The guarantee is per cell and does not cover provider shift, repeated-deployment multiplicity, release frequency, or unbounded raw severity; the terminal fiveendpoint experiment is a separate population-level analysis.
Experiments Prospective protocol. The target is a synthetic law P over cloud environments. The terms prespecified and registered mean fixed in an immutable internal record before the corresponding outcome bank opened; they do not refer to an external timestamped registry. Before outcomes, 128 clusters are drawn i.i.d.; each has four repeated contexts, not four independent samples: horizons 8 and 24 crossed with moderate and strong correlation. Per environment–context cell, Fit uses 128 scenes; Build 512, split 256/256 between Search/Plan and Cover; Screen 512, split 256/256 between Route and Guard; Certification 8192; and untouched Evaluation 512. These are role-independent simulator draws from P: 8192 pairs are not future production windows and require a trusted, inexpensive scenario generator. Policies share physical banks, common random numbers, endpoints, and replays. Four public traces from three provider families are descriptive cases (Verma et al. 2015; Cortez et al. 2017; Zhang et al. 2026); they are not additional draws from P. Development-B freezes the generator, budget, and fallback order selected by the prespecified 40-cell Development-B rule. Each formal cell commits its H0 −1 incumbent before CARA Search; the primary terminal comparison uses common Evaluation scenes. Ordinary failure retains that action as an intention-to-treat zero. If the frozen roster returns none within contract, all policies receive the pre-Search structural H0 action and an exact zero. The decision pipeline is not rerun; after an execution interruption, only a precommitted Evaluation-only procedure may reconstruct an already fixed reference target. Of 512 cells, 40 used structural H0 , and all recovery paths remain in the report. There were 3 recovery cells. Comparators and budgets. The roster is Global96, ProjBlind-2H, verified evacuation, ILS, and ALNS. Global96 replays 96 FFD orders under the common model. ProjBlind-2H matches CARA’s incumbent, seeds, eligible blocks, complete action universe, m, P , and deduplication, but uses a fixed unprojected directional-mass order; it isolates the certificate order and its bound. The remaining methods cover one-host
and broader local repairs. All target the same committed host count and role-separated data. Method-specific work contracts are prospectively frozen because nodes, replays, and local-search moves are unlike units; wall time, replays, memory, caps, and empty sets are retained. Confirmatory rule. For endpoint e, let ∆i,e average the four paired Evaluation differences within environment cluster i. Conditional on the frozen preformal design, the fixed pipeline and i.i.d. draws from P make ∆1,e , . . . , ∆128,e i.i.d. cluster-level observations. Let U.95,e be the one-sided Student upper endpoint for µe = EP [∆i,e ] at component level .05. Let ne,− , ne,+ , ne,0 count negative, positive, and tied cluster differences. The sign estimand is the non-tie probability πe− = PrP (∆i,e < 0 | ∆i,e ̸= 0), with null sign H0,e : πe− ≤ 1/2. Conditional on ne,− + ne,+ , psign e is the upper tail of Bin(ne,− + ne,+ , 1/2) at ne,− . Advancement requires U.95,e < 0,
psign ≤ .05 e
∀e ∈ {J, V, R, S, raw},
∆J ≤ −.005. (12) The Student endpoint is finite-sample exact for i.i.d. normal cluster differences and otherwise a finite-variance asymptotic approximation. The sign component is exact at πe− = 1/2, conditional on the non-tie count under i.i.d. cluster draws; it makes no unconditional tie claim. Requiring both targets mean and prevalence. Full component level is valid for the single intersection–union claim, not separate discoveries; the .005 J rule is an observed-effect safeguard, not a population-effect confidence claim. Every assignment is also recounted to its committed H0 − 1 or structural-H0 target. The supplement reports all terminal states, component statistics, diagnostic sensitivities, and the separate sizing calculation for nC = 8192; none alters Eq. (12). Registered ITT effect. The registered analysis passed without exclusions. Table 1 retains all 512 cells, including 40 structural-zero and 3 recovery cells. Every CARA-minus-incumbent difference was negative in all 128 environment clusters on every endpoint. The absolute J reduction was 3.57 percentage points; relative reductions in J, V, R, S, and raw burden were 3.7%, 21.4%, 23.1%, 28.2%, and 28.2%. These are synthetic-burden changes at a fixed host target, not an absolute SLA claim. Table 2 adds the complete frozenpolicy roster: CARA improves every displayed burden over Global96, ILS, ALNS, and the frozen incumbent, while ProjBlind-2H remains slightly better on point estimates. All policies average the same 26.63 deployed hosts. Context and shifted-action robustness. After the registered decision, we retained the fixed Cartesian products rather than selecting a favorable slice. Across four contexts and five endpoints, all 20 CARA-minus-incumbent point estimates and all one-sided Student upper endpoints under a single Bonferroni family were below zero. Context-specific ∆J ranged from −0.0550 (H = 8, strong correlation) to −0.0166 (H = 24, moderate). This
Figure 3: Environment-level ∆J for CARA minus the frozen incumbent; lower is better. Context rows show descriptive two-sided 95% Student intervals. The overall row averages contexts within environment and shows the registered one-sided 95% upper endpoint. Vertical lines mark zero and the separate observed-effect safeguard −.005. audit is post-outcome descriptive and cannot override the confirmatory decision. Fresh shifted-Evaluation replay of the fixed terminal b U.99 ) = actions passed all five components: for J, (∆, (−.00173, −.00127) with sign counts 99/11/18; each continuous endpoint had 128/128 negative environment differences and U.99 < 0 (all sign p < .0001). This neither reruns nor validates OOD selection or release. The complete supplement table retains both H = 24 J context failures; slices cannot replace the environmentcluster-averaged screen. Claim layers. Theorem 1 gives finite combinatorial exactness for the local order; Theorem 2 gives per-cell conditional Type-I control for one fixed action. Evaluation’s mean procedure is finite-sample exact only for normal cluster differences and otherwise asymptotic, while its sign test is finite-sample exact conditional on non-ties. None implies another. Matched order sensitivity and search feasibility. The matched comparison between CARA and ProjBlind-2H holds the incumbent-augmented seed/block/action universe fixed and changes only the structural order and admissible bound. All 469 applicable CARA searches returned the full exact top-16 without a node or bound cap. Route changed the provisional winner in 164 cells, and fresh Certification rejected 24 routed actions, leaving 445 releases. Thus the held-out and fresh stages materially participate in the terminal rule. CARA and ProjBlind2H release 445/512 and 448/512 actions; final actions match in 328 cells. The five observed comparator gaps are only 0.88–1.37% of the corresponding CARA-incumbent gains, but every point estimate favors ProjBlind-2H; neither superiority nor equivalence was registered or established. Their policy-specific work units and timer scopes differ, so no cost ratio is reported. Exact-prefix oracles pass. In the predeclared largest Fit-tree case, exact top-16 Search visited 117,095/5,459,984 nodes (2.14%; 97.86% below the no-pruning inventory) in 97.1 seconds; neither cap was binding, and conservative whole-process peak
A. Registered effect vs. incumbent Endpoint
CARA
B. Matched order sensitivity
∆I [U ] ProjBlind
Inc.
∆P [U ] n− /n+ /n0
J 0.9323 0.9679 -0.0357 [-0.0324] 0.9320 +0.0003 [+0.0007] V 0.1506 0.1915 -0.0409 [-0.0383] 0.1500 +0.0005 [+0.0009] R 0.0132 0.0171 -0.0040 [-0.0037] 0.0131 +0.0001 [+0.0001] S 0.0471 0.0656 -0.0185 [-0.0174] 0.0468 +0.0003 [+0.0004] Raw severity 0.000471 0.000656 -0.000185 [-0.000174] 0.000468 +0.000003 [+0.000004]
37/53/38 28/79/21 33/74/21 26/81/21 26/81/21
Table 1: Registered ITT effect and matched order sensitivity over 128 environment clusters; lower is better and brackets contain one-sided U.95 . Panel A passed all registered mean and sign gates (each 128/0/0, ps < .0001). Panel B is descriptive and supports neither order superiority nor equivalence. Policy CARA Global96 ProjBlind-2H Frozen incumbent ILS ALNS
J
V
R
S
Raw
Fallback rate
0.9323 0.9464 0.9320 0.9679 0.9651 0.9679
0.1506 0.1612 0.1500 0.1915 0.1907 0.1915
0.0132 0.0144 0.0131 0.0171 0.0170 0.0171
0.0471 0.0530 0.0468 0.0656 0.0649 0.0656
0.000471 0.000530 0.000468 0.000656 0.000649 0.000656
0.131 0.451 0.125 0.078 0.967 1.000
Table 2: Complete intention-to-treat Evaluation means for the six frozen policies; lower is better. No policy or endpoint was selected for display, and all policies share the same mean host count. Fallback includes execution of the policy’s committed reference action. RSS was 4.20 GiB. This is one feasibility point, not a scaling law. Public-trace coverage boundary. The complete dependent funnel is 20 attempts → 5 candidate-bearing episodes → 3 short screens → 0 releases: 15 searches are empty, two episodes fail raw direction, and three fail every screen component. All finish within cap. A complete post-hoc geometry audit explains every empty search: each 48-VM incumbent had eight six-VM hosts, so every two-host union had 12 items and lay outside the registered m ≤ 8 neighborhood. The five Borg-d attempts instead had 50–2,194 eligible blocks, returned all 16 requested candidates, and visited at most 185,955 nodes. Overlapping histories and cohorts make this a fixed-neighborhood coverage diagnosis, not external efficacy evidence.
Limitations Guarantee boundary. Theorem 1 certifies objective fidelity inside the registered two-host action class when inventory and replay are complete, arithmetic resolves, and work caps do not bind. It is not a global packing guarantee. Theorem 2 controls a single fixed action’s four-way false-improvement release under the stated conditional sign-independence and continuous-moment paths. It does not cover raw severity, distribution shift, or repeated-deployment multiplicity. Exhaustive smallinstance and all-descendant checks verify the ordered prefix and pruning bound; independent traceability checks verify commit-before-open and one-use execution. These establish implementation fidelity, not the scientific correctness of the simulator law. Evidence boundary. The 128 independent clusters and the 8,192 Certification pairs per cell are draws from the registered synthetic law, so the workflow presupposes a trusted, inexpensive scenario generator. Static homogeneous hosts omit arrivals, migration cost, heterogeneity,
interference, and feedback. The public traces are named coverage cases rather than population draws, and the shifted replay tests fixed terminal actions rather than endto-end selection and release. Both terminal policies use the same host target: the result evaluates last-mile repair, not the upstream H0 → H0 − 1 decision or an absolute SLA.
Conclusion CARA makes adaptive simulator-based placement repair auditable by coupling exact local proposal recovery to a one-use fresh deployment comparison. Its packingspecific bound returns the declared distinct top-P , while fresh Certification controls false four-way improvement for the committed action independently of upstream search complexity. In the frozen study, the complete failclosed policy improved all five terminal endpoints over the incumbent in every environment cluster. The fiveendpoint incumbent-relative intersection–union test advanced; every Evaluation pair also retained exact precommitted host-target equality by construction. The durable contribution is the separation of proposal fidelity, decision validity, and terminal utility; broader action coverage and error control across repeated deployments are the next steps.
Use of Generative AI GPT-5.6 Sol was used for language polishing. All AIassisted revisions were reviewed and verified by the authors, who take full responsibility for the content of this paper.
References Alvim, A. C. F.; Ribeiro, C. C.; Glover, F.; and Aloise, D. J. 2004. A Hybrid Improvement Heuristic for the OneDimensional Bin Packing Problem. Journal of Heuristics, 10(2): 205–229. Angelopoulos, A. N.; Bates, S.; Candès, E. J.; Jordan, M. I.; and Lei, L. 2025. Learn Then Test: Calibrating Predictive Algorithms to Achieve Risk Control. The Annals of Applied Statistics, 19(2): 1641–1662. Angelopoulos, A. N.; Bates, S.; Fisch, A.; Lei, L.; and Schuster, T. 2024. Conformal Risk Control. In International Conference on Learning Representations. Berger, R. L.; and Hsu, J. C. 1996. Bioequivalence Trials, Intersection–Union Tests and Equivalence Confidence Sets. Statistical Science, 11(4): 283–319. Borges, Y. G. F.; de Lima, V. L.; Miyazawa, F. K.; Pedrosa, L. L. C.; de Queiroz, T. A.; and Schouery, R. C. S. 2024. Algorithms for the Bin Packing Problem with Scenarios. Journal of Combinatorial Optimization, 48(4): 34. Bouveret, S.; and Lemaître, M. 2009. Computing Leximin-Optimal Solutions in Constraint Networks. Artificial Intelligence, 173(2): 343–364. Chekuri, C.; and Khanna, S. 2004. On Multidimensional Packing Problems. SIAM Journal on Computing, 33(4): 837–851. Coffman, E. G.; Garey, M. R.; and Johnson, D. S. 1996. Approximation Algorithms for Bin Packing: A Survey. In Hochbaum, D. S., ed., Approximation Algorithms for NP-Hard Problems, 46–93. PWS Publishing. Cohen, M. C.; Keller, P. W.; Mirrokni, V.; and Zadimoghaddam, M. 2019. Overcommitment in Cloud Services: Bin Packing with Chance Constraints. Management Science, 65(7): 3255–3271. Cortez, E.; Bonde, A.; Muzio, A.; Russinovich, M.; Fontoura, M.; and Bianchini, R. 2017. Resource Central: Understanding and Predicting Workloads for Improved Resource Management in Large Cloud Platforms. In Proceedings of the 26th ACM Symposium on Operating Systems Principles, 153–167. Cox, D. R. 1975. A Note on Data-Splitting for the Evaluation of Significance Levels. Biometrika, 62(2): 441–444. Delorme, M.; Iori, M.; and Martello, S. 2016. Bin Packing and Cutting Stock Problems: Mathematical Models and Exact Algorithms. European Journal of Operational Research, 255(1): 1–20. Elmachtoub, A. N.; and Grigas, P. 2022. Smart “Predict, then Optimize”. Management Science, 68(1): 9–26. Gilmore, P. C.; and Gomory, R. E. 1961. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 9(6): 849–859. Grandl, R.; Ananthanarayanan, G.; Kandula, S.; Rao, S.; and Akella, A. 2014. Multi-Resource Packing for Cluster Schedulers. In Proceedings of the 2014 ACM Conference on SIGCOMM, 455–466. Laroche, R.; Trichelair, P.; and Tachet des Combes, R. 2019. Safe Policy Improvement with Baseline Bootstrapping. In Proceedings of the 36th International Confer-
ence on Machine Learning, volume 97 of Proceedings of Machine Learning Research, 3652–3661. PMLR. Laufer-Goldshtein, B.; Fisch, A.; Barzilay, R.; and Jaakkola, T. S. 2023. Efficiently Controlling Multiple Risks with Pareto Testing. In International Conference on Learning Representations. Lawler, E. L. 1972. A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem. Management Science, 18(7): 401–405. Lourenço, H. R.; Martin, O. C.; and Stützle, T. 2003. Iterated Local Search. In Glover, F.; and Kochenberger, G. A., eds., Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, 320–353. Springer. Luo, C.; Qiao, B.; Xing, W.; Chen, X.; Zhao, P.; Du, C.; Yao, R.; Zhang, H.; Wu, W.; Cai, S.; He, B.; Rajmohan, S.; and Lin, Q. 2021. Correlation-Aware Heuristic Search for Intelligent Virtual Machine Provisioning in Cloud Systems. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14): 12363–12372. Mandi, J.; Kotary, J.; Berden, S.; Mulamba, M.; Bucarey, V.; Guns, T.; and Fioretto, F. 2024. Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities. Journal of Artificial Intelligence Research, 80: 1623–1701. Martinovic, J.; and Selch, M. 2021. Mathematical Models and Approximate Solution Approaches for the Stochastic Bin Packing Problem. Computers & Operations Research, 135: 105439. McNemar, Q. 1947. Note on the Sampling Error of the Difference between Correlated Proportions or Percentages. Psychometrika, 12(2): 153–157. Murty, K. G. 1968. Letter to the Editor—An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research, 16(3): 682–687. Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An Analysis of Approximations for Maximizing Submodular Set Functions—I. Mathematical Programming, 14: 265–294. Ogryczak, W. 1997. On the Lexicographic Minimax Approach to Location Problems. European Journal of Operational Research, 100(3): 566–585. Pisinger, D.; and Ropke, S. 2019. Large Neighborhood Search. In Gendreau, M.; and Potvin, J.-Y., eds., Handbook of Metaheuristics, volume 272 of International Series in Operations Research & Management Science, 99– 127. Springer, 3 edition. Przybylski, A.; and Gandibleux, X. 2017. MultiObjective Branch and Bound. European Journal of Operational Research, 260(3): 856–872. Ramdas, A.; Grünwald, P.; Vovk, V.; and Shafer, G. 2023. Game-Theoretic Statistics and Safe Anytime-Valid Inference. Statistical Science, 38(4): 576–601. Ropke, S.; and Pisinger, D. 2006. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4): 455–472.
Roytman, A.; Kansal, A.; Govindan, S.; Liu, J.; and Nath, S. 2013. PACMan: Performance Aware Virtual Machine Consolidation. In Proceedings of the 10th International Conference on Autonomic Computing, 83–94. San Jose, CA: USENIX Association. ISBN 978-1-931971-02-7. Scholl, A.; Klein, R.; and Jürgens, C. 1997. BISON: A Fast Hybrid Procedure for Exactly Solving the OneDimensional Bin Packing Problem. Computers & Operations Research, 24(7): 627–645. Shafer, G.; Shen, A.; Vereshchagin, N.; and Vovk, V. 2011. Test Martingales, Bayes Factors and p-Values. Statistical Science, 26(1): 84–101. Song, Y.; Luedtke, J. R.; and Küçükyavuz, S. 2014. Chance-Constrained Binary Packing Problems. INFORMS Journal on Computing, 26(4): 735–747. Thomas, P.; Theocharous, G.; and Ghavamzadeh, M. 2015. High Confidence Policy Improvement. In Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, 2380–2388. PMLR. Verma, A.; Pedrosa, L.; Korupolu, M.; Oppenheimer, D.; Tune, E.; and Wilkes, J. 2015. Large-Scale Cluster Management at Google with Borg. In Proceedings of the Tenth European Conference on Computer Systems, 1–17. Wilder, B.; Dilkina, B.; and Tambe, M. 2019. Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1): 1658–1665. Yan, J.; Lu, Y.; Chen, L.; Qin, S.; Fang, Y.; Lin, Q.; Moscibroda, T.; Rajmohan, S.; and Zhang, D. 2022. Solving the Batch Stochastic Bin Packing Problem in Cloud: A Chance-Constrained Optimization Approach. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2169–2179. Zhang, X.; Shen, L.; Chen, M.; Li, Z.; Li, H.; Fu, H.; Sun, J.; Ren, X.; and Liu, C. 2026. CloudCons: A Comprehensive End-to-End Benchmark for Cloud Resource Consolidation. ArXiv preprint, arXiv:2606.13513. Zhang, Z.; Denton, B. T.; and Xie, X. 2020. Branch and Price for Chance-Constrained Bin Packing. INFORMS Journal on Computing, 32(3): 547–564.
Supplementary Material for CARA: Exact Local Repair and Fresh One-Action Certification Xiyang Zhang1,2 , Yuanhe Tian1∗ , Hongzhi Wang2 1
Zhongguancun Academy Harbin Institute of Technology [email protected], [email protected], [email protected] 2
Scope and Reading Guide This supplement provides proofs, experimental protocol, complete results, and robustness checks. Four boundaries matter: (i) CARA is exact only for its certificate order in the bounded neighborhood; (ii) matched ProjBlind-2H has a separate prefix that never feeds CARA; (iii) fresh Certification controls conditional false four-endpoint release, while raw/e-Guard are screens; and (iv) Evaluation tests five terminal endpoints. Neither exactness claim implies global optimality, order superiority, or release. Ordinary failure retains the H0 − 1 incumbent. If no frozen generator can construct one, the precommitted structural H0 action is assigned to both policies as an exact-zero intention-to-treat state. Family-integrity loss is irrecoverable rather than silently mapped to that state; statistical non-release in an available cell therefore preserves the existing host saving.
Incumbent, Structural Scaffold, and Action Class There are N VMs, T time coordinates, nonnegative scene loads xbit ≥ 0, and capacities Ct > 0. Fit estimates a factor–diagonal covariance model and constructs a fully replayed structural placement π str with H0 hosts. It defines feasibility and a fixed normalization, but is not the ordinary statistical comparator. Development-B contains ten independently seeded environments and four contexts. In each of its 40 cells, all five generators construct direct H0 − 1 actions using Fit and Build only. A disjoint direct-Evaluation view scores those fixed actions. Lower-is-better within-cell midranks are computed for J, V, R, S, and raw. The frozen rule first maximizes the number of eligible cells and then applies full leximin to the increasingly sorted 40 × 5 rank vector; fixed method order breaks a complete tie. This selects the first generator and the remaining fallback order. In a formal cell, generators are tried in frozen order on the committed Fit/Search/Plan view. The first nonempty output is reranked by the exact four-endpoint projectedcertificate key; the canonical physical action identity breaks ties.
∗
Corresponding author.
Its first action is the certificate-reranked frozengenerator incumbent π I . The action and selection rule are committed before any Screen, Certification, or Evaluation outcomes exist. If all registered generators are empty, the cell retains the structural H0 reference as an exact-zero intention-to-treat state; no post-outcome replacement is allowed. An outcome-frozen seed pool supplies verified H0 − 1 placements. For seed s and an unordered pair of its nonempty hosts (h1 , h2 ), let Us,h1 ,h2 be their item union. A block is eligible when 2 ≤ |Us,h1 ,h2 | ≤ m. All other hosts remain fixed, while the block contains every bipartition (A, U \ A) with both parts nonempty. The smallest mutable VM is fixed to the first replacement host, and replacement hosts are canonically relabeled, removing the two-way label symmetry. A complete leaf is replayed independently for item coverage, nonempty hosts, cardinality, capacity, covariance feasibility, and exactly H0 − 1 active hosts. A canonical action encoding deduplicates placements while preserving origins, and the unchanged incumbent is removed. The neighborhood is narrower than global packing and broader than one-donor evacuation: items may move both ways. Exact packing, ranked solutions, and multiobjective search remain prior art (Murty 1968; Coffman, Garey, and Johnson 1996; Scholl, Klein, and Jürgens 1997; Przybylski and Gandibleux 2017); the new object is the incumbent-relative admissible bound in the mixed certificate lattice.
Fixed-normalizer burdens For placement π and scene b, define X qbht (π) = xbit − Ct /Ct . i:π(i)=h
+
Let Db (π) count hosts with an overload beyond the registered tolerance, P Lb (π) count violating host–time pairs, and Eb (π) = h,t qbht (π). The bounded burdens are Jb (π) = 1{Db (π) > 0}, Vb (π) = Db (π)/H0 , Rb (π) = Lb (π)/(H0 T ), Sb (π) = min{Eb (π)/(κH0 T ), 1}. (1) Raw severity ub (π) = Eb (π)/(H0 T ) is stored separately. Guard uses ρb (π) = ub /(ub + κ) because betting factors
Claim
Assumptions
Validation evidence
Not implied
Exact CARA prefix; ideal matched prefix separately
Complete common action inventory; nonnegative loads; resolved CARA arithmetic; caps not hit; ideal special-function evaluation for matched proposition Fresh paired Certification bank; fixed incumbent, action, and plans; conditional sign-dominance and independence given the transcript and realized discordance set; one moment path per continuous endpoint Fixed routed action; disjoint Guard rows; pre-row conditional bounded no-harm nulls for e-Guard 128 i.i.d. draws from the registered synthetic environment law; zero-margin mean superiority and tie-conditional sign dominance on five endpoints
Per-order exhaustive comparison; strict-only pruning; complete feasibility checks and action deduplication
A pooled union; global, cross-order, or Pareto optimality; all-input binary64 special-function exactness Provider-shift robustness, raw-severity improvement, or high release rate
Conditional false-improvement control
Held-out raw/Guard screens
Evaluation all-five claim
Prespecified one-use bank access, exact McNemar tail, exact integer products, and no candidate retry
Exact raw Q53 direction, fixed mixtures, threshold 100 Complete 128 × 4 × 512 table and per-cell committed-target assignment recount
Population raw inference; false-veto control for the raw gate or conditional on its pass Population inference from four public traces (three provider families) or realized power from a design model
Table 1: Claims, assumptions, and boundaries. require bounded increments; its mean does not identify the mean of ub . Both π I and π use the same H0 denominator and exactly H0 −1 hosts, so the comparison changes neither exposure nor structural host count.
Exact Incumbent-Relative Certificate Search Write nB for Search/Plan size, nC for Certification size, and r = nC /nB ∈ N; here nB = 256, nC = 8192, and r = 32. For J, A counts candidate-only harmful Build discordances and B counts incumbent-only harmful discordances. Define pJ (A, B) = Pr{Bin(r(A + B), 1/2) ≤ rA}, θJ (A, B) = log(1/20) − log pJ (A, B). (2) For e ∈ {V, R, S}, let M = 253 and, for stored binary64 z ∈ [0, 1], define the closed-midpoint count k + 1/2 C53 (z) = k ∈ {0, . . . , M − 1} : ≤z M = ⌊M z + 1/2⌋. (3) Thus C53 (z) ∈ {0, . . . , M } and |C53 (z)/M − z| ≤ 1/(2M ). Put dei = C53 (ei (π I )) − C53 (ei (π)), Xei = (dei − 1)/(M + 1). (4) dei ∈ [−M, M ] and Xei ∈ [−1, (M − 1)/(M + 1)], so all registered betting factors are strictly positive. The Build fitter exhausts j ∈ {0, . . . , 255} and computes nB X j ge (j) = log 1 + Xei , 256 i=1 be (j) = roundeven {240 ge (j)}. (5) It maximizes (be (j), ge (j), −j) lexicographically under the specified binary64 log1p/fsum rule and fixes λe = je /256. Search then encloses nB X θe = r log(1 + λe Xei ) − log 20 (6) i=1
from the exact rational factors. These target-size quantities are ranking margins, not evidence from the future Certification bank. Certificate-form alignment. Fix an action and λe before both Build and Certification panels, and suppose their rows are i.i.d. from the same conditional law.PFor Ye = log(1 + λe Xe ), rnB = nC gives nB E[r i=1 Yei − log 20] = nC EYe − log 20. Moreover Ye ∈ [− log 256,P log 2]. Applying Hoeffding to the fresh nC sum log We = i=1 Yei proves the bound in the main text whenever EYe > log 20/nC . The fixed-pair premise is essential: adaptive Build selection prevents interpreting the observed projection as an unbiased post-selection estimate or confidence bound.
Lattice key and traversal
Let η = 2−40 . Directed intervals for each θe are refined until their lower and upper endpoints have the same ηfloor. The corresponding integer se = ⌊θe /η⌋ is then unique. A leaf key sorts its four labeled scores increasingly and compares the vectors lexicographically; only a complete evidence tie reaches the canonical physical assignment. Proposition 1 (conjunctive lattice margin). For C = {s ∈ Z4 : se ≥ 0 ∀e}, sup{δ ∈ Z : s − δ1 ∈ C} = min se . e
Full leximin first maximizes this signed uniform-shift margin and, conditional on a tie, recursively maximizes every remaining bottleneck. Proof. Membership after a shift is equivalent to δ ≤ se for every coordinate. The largest feasible shift is therefore the minimum coordinate. Sorting exposes that minimum first; fixing equal leading coordinates and repeating proves the recursive claim. □ Search iterates the canonical seed–block inventory, applies the symmetry break, and recursively assigns the remaining mutable VMs. At a complete node it replays all physical constraints, fits the three plans, resolves the lattice key, deduplicates the action, rejects π I , and updates an ordered top-P set. A partial node first applies
the hereditary structural check below; otherwise it computes the evidence bound. Once P distinct actions exist, evidence pruning requires the optimistic sorted vector to be strictly below the current P th vector. An arithmetic ceiling, node cap, or bound cap exposes no partial prefix and returns the incumbent path.
Admissibility of the partial bound Lemma (monotone structural pruning). If a partial replacement host exceeds the physical cardinality cap or its fitted mean load exceeds capacity (including the registered tolerance) at any time, no descendant is valid. Proof. Every descendant only adds VMs to that host. Cardinality and every fitted mean-load coordinate are therefore nondecreasing because fitted item means are nonnegative. Covariance is not partially pruned; it is replayed at each complete leaf. □ Let Fn (k) = Pr{Bin(n, 1/2) ≤ k}. Conditioning on the last Bernoulli trial gives Fn+1 (k + 1) = 21 Fn (k + 1) + 12 Fn (k) ≥ Fn (k),
(7)
Fn (k) = 21 Fn−1 (k) + 12 Fn−1 (k − 1) ≤ Fn−1 (k).
(8)
Lemma 1 (projected McNemar monotonicity). Turning one partial candidate J value from zero to one cannot increase θJ for any positive integer projection ratio r. Proof. If the incumbent bit is zero, (A, B) becomes (A + 1, B); repeated use of Eq. (7) shows that the projected lower-tail probability cannot decrease. If the incumbent bit is one, (A, B) becomes (A, B − 1); repeated use of Eq. (8) gives the same conclusion. Since − log p is nonincreasing in p, the margin cannot improve. □ Omitting unassigned VMs produces componentwise lower candidate burdens because loads are nonnegative. Adding an item can only decrease each incumbent-minuscandidate midpoint difference. For fixed nonnegative λ, log(1 + λX) is increasing in X. Lemma 2 (plan-independent continuous bound). At a partial node v, let Xi (v) be the corrected difference obtained by omitting unassigned VMs. For every descendant action a, its fitted 0 ≤ λa ≤ 255/256 satisfies 255 X θe (a) ≤ r max{Xi (v), 0} − log 20 =: θe (v), 256 i (9) The outward upward lattice rounding of θe (v) bounds every descendant score, independently of the descendant’s fitted plan. Proof. Partial differences satisfy Xi (v) ≥ Xi (a). Since Xi (a) ≥ −1 and λa < 1, each factor is positive and log(1 + λa Xi (a)) ≤ λa Xi (a) ≤ (255/256) max{Xi (v), 0}. Summation, multiplication by r, subtraction of log 20, and upward rounding preserve the inequality. For S, the implementation uses zero partial severity, a looser bound that remains valid by nonnegativity. □ Lemma 3 (sorting preserves optimism). If ue ≥ ve for every labeled coordinate, then the kth increasing order statistic of u is at least that of v for every k.
Proof. Otherwise at least k components of u would lie below the kth order statistic of v. Their labeled counterparts in v are no larger, which contradicts the definition of that order statistic. □ Theorem 1 (incumbent-anchored exact neighborhood top-P ). Let A(π I ) be all distinct, replay-valid actions other than π I in the registered seed–block neighborhood. If the typed inputs validate, all required replays and arithmetic intervals resolve, and neither work cap is reached, strict-only branch-and-bound returns the first min{P, |A(π I )|} actions under the decreasing fullleximin lattice key followed by increasing canonical physical assignment. Proof. The symmetry-broken tree represents one copy of every nonempty bipartition. The structural-pruning lemma discards no valid completion, and Lemmas 1–3 make the partial sorted key optimistic for every descendant. A subtree pruned on a strict evidence loss cannot contain an action that enters the retained prefix. Equality is never pruned before its physical tie row is known. Complete replay removes exactly invalid leaves; global canonical encoding merges only identical assignments; explicit anchor rejection removes only π I . Induction over the deterministic traversal therefore yields the same ordered distinct-action prefix as exhaustive enumeration. □ With S seeds and at most H hosts per seed, there are at most S H2 blocks and O(2m ) structural nodes per eligible block. Under the fixed precision schedule and work caps, replay, plan fitting, interval resolution, and top-P maintenance have finite cost per node. Given the seeds, the structural node count is fixed-parameter tractable in m; seed generation lies outside this bound. No claim is made for unrestricted global bin packing or unit-cost transcendental arithmetic. Exact recovery in Theorem 1 means fidelity to the registered certificate objective. It does not assert that this objective is statistically or operationally superior to another proposal order.
Ideal-Arithmetic Prefix for the Matched Directional Comparator ProjBlind-2H is a separate matched comparator. It uses the same committed seed authority, eligible two-host blocks, symmetry break, complete physical replay, incumbent exclusion, and canonical physical action identity as Section . It differs only in its Build ranking, and its prefix never enters CARA Cover, Route, or Certification. Let xeb (π) be action π’s bounded burden for e ∈ {J, V, R, S} on Build scene b, and let xeb (π str ) be the fixed structural-reference burden. Define the candidateonly and reference-only directional masses X Ae (π) = [xeb (π) − xeb (π str )]+ , b
X Be (π) = [xeb (π str ) − xeb (π)]+ .
(10)
b
For J these are integer discordance counts; for V, R, S they are nonnegative fractional masses. They are deter-
ministic Build ranking surrogates, not Certification pvalues. For nonnegative A, B, write g(A, B) = log(1/20) − log I1/2 (B, A + 1), q(A, B) = F⌈A⌉+⌊B⌋ (⌈A⌉),
d(A, B) = B − A, (11)
where I is the regularized incomplete beta function, its registered B = 0 limit is one, and Fn (k) = Pr{Bin(n, 1/2) ≤ k}. On integer masses, the fractional tail in g equals the one-sided conditional McNemar tail; q is its conservative exact-grid anchor for fractional masses. Put ge (π) = g(Ae (π), Be (π)), and analogously define qe (π) and de (π). The directional key compares, in order, (sort↑ {ge (π)}e , sort↓ {qe (π)}e , sort↑ {de (π)}e ) . (12) The first and third rows are lexicographically maximized, while the second is lexicographically minimized. The registered unary 2−40 comparison buckets are applied to the finite binary64 entries of the first and third rows. Comparator equality is broken by increasing canonical physical assignment. This defines a deterministic total order on distinct actions.
Node optimism and exactness At depth d, unassigned block VMs are omitted. By nonnegative loads, every complete descendant z has (d) (z) xeb ≤ xeb for every labeled endpoint and scene. Relative to the fixed xeb (π str ), positive-part monotonicity gives (z) A(d) Be(d) ≥ Be(z) . (13) e ≤ Ae , The implemented node bound does not rely on ideal real arithmetic. Let N be the Build panel size, let u = 2−53 be binary64 unit roundoff, and define the registered absolute radius εN = min{N, 8(N + 1)2 u}. (14) For J, masses are exact counts. For V and R, the node reduces exact integer directional numerators, divides once, subtracts εN from the harmful-mass center and adds it to the beneficial-mass center, clips to [0, N ], and takes one outward nextafter step. For S, it uses the universal candidate lower burden zero, hence harmful mass zero, and adds the same radius plus an outward step to the fixed-reference sum. To justify the radius, every replayed burden and positive-part term lies in [0, 1]. Applying the standard binary64 model to the two divisions, subtraction, positive part, and final faithfully rounded sum gives absolute forward error at most 8(N +1)2 u whenever 8(N +1)u < 1; the registered N = 256 is in this regime. If the expression is not informative, clipping εN to N returns the whole possible mass range. Thus the additional outward step encloses the corresponding complete binary64 replay in all cases. Lemma (ideal directional RB node optimism). With the incomplete-beta component evaluated in ideal real arithmetic, the conservative directional key at any visited node is no worse than the exact key of every physically feasible complete descendant.
Proof. For positive shapes, write a beta variate as Y /(Y + Z) with independent gamma variables of shapes B and A + 1. Increasing B couples by adding an independent gamma increment to Y and shifts this ratio upward; increasing A adds an independent gamma increment to Z and shifts it downward. Hence decreasing A or increasing B cannot increase the incomplete-beta lower tail at 1/2; the registered zero-shape limit has the same direction. Equation (13) therefore makes g optimistic. The same mass changes cannot increase the exact-grid McNemar tail q, by the binomial recurrences in Eqs. (7)–(8), and cannot decrease B − A. Outward mass envelopes preserve these directions against complete binary64 replay. Labeled componentwise dominance preserves all three sorted order-statistic rows, and the unary comparison buckets are monotone. Hence the complete node key is no worse than every descendant key. □ Proposition 2 (matched directional ideal prefix). Let A(π I ) be the registered bounded two-host family in Theorem 1. If typed inputs validate, all required physical replays finish, the registered work cap is not reached, and I1/2 is evaluated exactly, the ideal directional search returns the first min{P, |A(π I )|} distinct actions under Eq. (12) and the canonical physical tie row. Proof. For every verified seed, every unordered eligible host pair is visited. Fixing the smallest mutable VM to the first replacement host enumerates each unordered nonempty bipartition once within a block. Hereditary cardinality and fitted mean-capacity failures remove no feasible completion; covariance is checked only at leaves. By the ideal directional node-optimism lemma, a node whose key is strictly worse than the current P th complete action cannot enter the retained prefix. Comparator equality is not pruned because the descendant’s canonical physical tie row is unknown. Every surviving leaf receives complete feasibility and endpoint replay; incumbent exclusion precedes top-P insertion; canonical assignment merges only the same physical action across seeds and blocks. Sorted insertion and truncation therefore maintain the same distinct-action prefix as exhaustive enumeration throughout the deterministic traversal. □ If a work cap is reached or a required replay or arithmetic operation does not resolve, the comparator discards its partial retained list. The implemented comparator evaluates the incomplete beta function in binary64; exhaustive small-instance parity checks its returned prefix, but we do not claim that the library evaluation preserves every ideal 2−40 bucket on all possible inputs. Proposition 2 is therefore an ideal-order guarantee, not an all-input executable special-function theorem. It neither ranks that order above the certificate objective nor changes CARA’s one-fixed-action Certification theorem.
Arithmetic Contract and Q53 Transfer Binary64 logs are used only in the Build plan-selection rule. Once j is fixed, each continuous factor is the positive rational 256(M + 1) + j(di − 1) . (15) 256(M + 1)
Equal factors are grouped and powered before multiplication. Certification compares exact integer numerator N and denominator D through the inclusive inequality N ≥ 20D. Search evaluates logarithms under a fixed precision-doubling schedule with outward rounding. Refinement stops only when both bounds occupy one lattice cell; crossing a boundary at the ceiling raises a typed unresolved result. The binary component uses exact binomial recurrences and rational bounds. Independent tests cover zero, adverse, favorable, threshold-adjacent, and near-lattice inputs. Lemma 4 (Q53 correction transfers the mean null). For stored a, b ∈ [0, 1], let d = C53 (b) − C53 (a). Then d−1 M (b − a) ≤ . (16) M +1 M +1 Thus, for any sigma-field K, E[b − a | K] ≤ 0 implies E[(d − 1)/(M + 1) | K] ≤ 0. Proof. Under the executable closed-midpoint convention, M z − 1/2 ≤ C53 (z) ≤ M z + 1/2. Subtracting the lower bound for C53 (a) from the upper bound for C53 (b) yields d ≤ M (b − a) + 1. Conditional expectation preserves the resulting inequality. □
Conditional Certification Guarantee Let Θ denote fixed environment parameters and let T− be the complete transcript through e-Guard: the structural scaffold, incumbent, routed action, three fitted plans, all earlier outcomes and decisions, and the endpoint definitions. It excludes the Certification innovations and all endpoint values determined by them. Put H− = σ(Θ, T− ). Prespecified Certification row labels may occur in T− only as ancillary indices: conditional on Θ, fresh innovations follow the registered law independently of the upstream transcript. In particular, the statistical argument does not condition on a latent random-state variable that determines those innovations; the audit record checks this separation but is not itself an independence assumption. The routed action and each Build-selected λe ∈ [0, 255/256] are H− -measurable. For J, condition further on the realized discordance set D. Assume the discordant signs are independent given (H− , D); under HJ , sign i is candidate-only harmful with conditional probability pi ≥ 1/2. Their sum is therefore a Poisson–binomial variable that stochastically dominates Bin(|D|, 1/2), making the fair-binomial lower tail superuniform. For each e ∈ {V, R, S}, validity may be established under either registered null path: 1. Heseq (sequential mean): E[Xei | H− , Xe,<i ] ≤ 0 for every row. 2. Heind (independent average mean): the rows are indeP pendent given H− and n−1 E[X ei | H− ] ≤ 0. C i Below, He denotes the applicable registered path. The second permits heterogeneous row means but not serial dependence; the first permits history-adaptive laws but not later negative means compensating for a positive conditional mean. Sufficient conditions in the original burden scale are, respectively, E[ei (π I ) − ei (π) | H− , Xe,<i ] ≤ 0 for every i, or conditionally independent paired rows
P I with n−1 C i E[ei (π ) − ei (π) | H− ] ≤ 0. Lemma 4 transfers these inequalities to Xei ; conditional independence is inherited by the deterministic Q53 transforms. Lemma 5 (continuous component level). Under either path, (n ) C Y Pr (1 + λe Xei ) ≥ 20 | H− ≤ .05. i=1
Proof. Under the sequential path the product is a nonnegative supermartingale with conditional expectation at most one. Under the independent path, writing µi = E[Xei | H− ], factorization and AM–GM give Y E[WnC | H− ] = (1 + λe µi ) i
!nC ≤
1 + λe n−1 C
X
µi
≤ 1.
i
All random factors and all AM–GM terms are positive: Xei ≥ −1 and µi ≥ −1 give 1 + λe Xei ≥ 1/256 and 1 + λe µi ≥ 1/256. Markov’s inequality completes either path. □ Theorem 2 (conditional false-improvement release). If at least one of HJ , HV , HR , HS is true, the probability that the exact McNemar component and all three fixedwealth components pass is at most .05, conditional on H− . Proof. Conditional on (H− , D), couple each independent Bernoulli(pi ) sign with a fair Bernoulli by common uniforms. The former sum is no smaller almost surely, so the fair-binomial lower-tail test is conservative after averaging over D. The binary component is therefore level .05 conditional on H− ; Lemma 5 gives the same level for each continuous component. Under the intersection– union null, joint release is contained in at least one truenull rejection event. Its conditional probability is therefore at most .05; no Bonferroni split is needed. □ This is a terminal-product result, not an anytime claim (Shafer et al. 2011; Ramdas et al. 2023). It applies to one action fixed before its bank. It does not cover raw severity, cross-policy familywise error, population shift, or the probability that Search finds an action worth releasing.
Held-Out Choice, Direction Gate, and e-Guard Build and Screen are split by outcome-free identities. Search/Plan generates and scores actions. Cover receives only the exact top-P prefix and replays it on four fixed folds. For a held-out panel G, it recomputes the projected J margin and the three fixed-plan margins without refitting. If saf e is action a’s endpoint lattice score on fold f , exact midranks first map each endpoint among actions to raf e ∈ [0, 1]. Put baf = mine raf e and midrank these bottlenecks again to obtain qaf . Cover exhausts 4
Sb ∈
1X max qaf , a∈S ∅̸=S⊆[P ], |S|≤K 4 arg max
K = min{4, P }.
f =1
(17)
P4 For P ≤ 16, at most k=1 16 = 2,516 subsets are k examined. Equal values prefer the smaller set, then Search order and the canonical physical action identity. Route replays this portfolio on a disjoint Screen half and chooses one action by full leximin of endpoint ordinals centered at the zero certificate boundary. It cannot generate a new action or refit a plan. The complementary Screen half goes only to the routed winner. For any finite nonnegative binary64 raw severity, define the unbounded integer count raw C53 (u) = ⌊253 u + 1/2⌋.
The raw-direction gate requires X raw raw {C53 (ui (π I )) − C53 (ui (π)) − 1} ≥ 0.
(18)
i∈G raw raw Because C53 (b)−C53 (a)−1 ≤ 253 (b−a), passing implies a nonpositive candidate-minus-incumbent raw mean on these held-out rows. The count is evaluated with unbounded integer arithmetic, so the gate does not clip large finite raw values. This is an observed-sample direction check only; it supplies neither a population tail bound nor a raw-severity safety certificate. The raw gate and e-Guard use this same once-opened row batch; the former is not a data split for the latter. Before any outcome in G is opened, let TG contain the fixed environment parameters, routed action, incumbent, transforms, row identities and order, but neither a Grow outcome nor PRNG state determining one, and put FG = σ(TG ). For e-Guard, let M = 253 and use the same closed-midpoint map CM (z) = |{k ∈ {0, . . . , M − 1} : (k + 1/2)/M ≤ z}| = ⌊M z + 1/2⌋ ∈ {0, . . . , M }. Let ρ = ψκ (u) and EG = {J, V, R, S, ρ}. Define candidateminus-incumbent increments
ZiJ = Ji (π) − Ji (π I ), hie = CM (ei (π)) − CM (ei (π I )), Zie = (hie − 1)/(M + 1), e ∈ {V, R, S, ρ}. (19) Here hie ∈ [−M, M ] and Zie ∈ [−1, (M −1)/(M +1)]. The registered fixed mixture is 255 j 1 XY 1+ Zie . (20) Ge = 255 j=1 256 i∈G
Guard vetoes iff some Ge ≥ 100; equality vetoes. Products and the mixture comparison are evaluated with exact integers. Readiness and signed gains are reported only as diagnostics. No alarm forwards the same winner; it neither certifies no harm nor unlocks another portfolio action. Proposition 3 (e-Guard false-veto control). Condition on FG . Suppose all five transformed candidate-minusincumbent no-harm nulls hold conditionally. For each endpoint assume either E[Zie | FG , Z<i,e ] ≤ 0 for every row, P or conditional independence given FG with |G|−1 i∈G E[Zie | FG ] ≤ 0. Let EG be the operational event that the raw-direction gate passes and the
Terminal action
Trigger
Candidate
All four fresh Certification components pass Committed in- Empty/capped/unresolved Search, cumbent failed raw direction, e-Guard veto, or ordinary Certification non-release Precommitted re- One preauthorized Evaluation-only recovery target construction after an execution interruption, using a durable pre-Search incumbent or structural reference; the recovery status is retained for all six policies Structural scaffold No eligible incumbent; assigned to every policy before Search as an exactzero intention-to-treat state No analyzable ter- The complete committed target cannot minal be reconstructed; the irrecoverable cell blocks the complete 512-cell analysis and every formal claim
Table 2: Terminal semantics. subsequent e-Guard vetoes. Then X Pr{EG | FG } ≤ Pr{Ge ≥ 100 | FG } ≤ .05. e∈EG
(21) Proof. For fixed j, every factor is nonnegative because Zie ≥ −1 and j/256 < 1. The sequential path makes the product a nonnegative supermartingale; under the independent path, factorization and AM–GM bound its expectation by one. Averaging preserves that bound. Markov gives .01 per endpoint, and the union bound over five endpoints gives .05. □ S The first inequality uses EG ⊆ e {Ge ≥ 100}; it does not condition on the data-dependent raw-pass event. The proposition therefore limits an unnecessary e-Guard veto under the five pre-row conditional bounded nulls, but does not control rejection by the raw-direction gate or give a bound after conditioning on its pass. It gives no bound on missed harm. Its raw coordinate concerns ρ, not the unbounded mean of u, and is not used in Theorem 2. Before Certification is opened, the policy roster, incumbent, admitted action, fixed plans, endpoint definitions, scene order, and bank identity are recorded as immutable. The bank is opened once and evaluated on a common paired table. An ordinary failed component assigns the incumbent action to that policy. A process failure that compromises family completeness is irrecoverable unless a separately prespecified recovery procedure can reconstruct the exact pre-Search target; it is never silently relabeled as a statistical zero. Reopening the bank is prohibited, and Evaluation begins only after the terminal action for every policy is fixed.
End-to-end information boundary Table records what each stage can read and what it must commit before the next bank opens. This is more than an implementation convention: Theorem 2 conditions on the entire transcript through e-Guard, so the routed action and its plans must be immutable before the frozen execution materializes Certification outcomes. Evaluation is later still and cannot alter a failed Certification decision. Ordinary rejection is represented by the committed in-
Stage
Reads
Development-B
Its disjoint Fit, Build, and direct Evaluation views Incumbent establish- Formal Fit and Search/Plan ment view Search / Cover / Search/Plan, held-out Cover, Route then disjoint Route rows Raw direction / e- Remaining Screen rows for the Guard routed action only Certification One fresh paired bank for the fixed action and incumbent Evaluation / report Immutable terminal actions and the common Evaluation bank
Commits before advancing
Excluded until later stage
Generator order, fallback order, and resource contracts First verified H0 −1 action from the frozen generator order, including its assignment and physical identity Exact top-P , nonempty portfolio, one routed action, and fixed continuous plans Forward-or-veto decision; no retry handle or portfolio access Four component decisions and the terminal action All six policy rows, host recounts, recovery indicators, and the complete analysis
All formal banks and all publictrace outcomes Screen, Certification, and Evaluation Guard rows until routing; all Certification and Evaluation rows Certification and Evaluation Evaluation No authority to revise an action, gate, cell roster, or hypothesis
Table 3: Data-access and commitment boundary. “Excluded” indicates that the stage does not use outcomes from that bank under the prespecified execution order; it is an audited dependency restriction rather than a claim of physical or cryptographic isolation. cumbent, so it contributes a paired zero to the intentionto-treat analysis. An execution interruption is different: the original bank cannot be reused, and only the prespecified Evaluation-only procedure in Table may reconstruct the incumbent or structural-target zero. The recovery indicator is retained for all six policies during aggregation. Study-integrity note. Formal results are based on a single execution initiated after validation of the analysis pipeline. Earlier validation runs were excluded before endpoint analysis: no endpoint estimate from them was computed, inspected, or used to choose a method, threshold, hypothesis, or analysis rule. Corrections were restricted to execution safeguards and representation; the action class, endpoints, budgets, and statistical contract were unchanged.
Experimental Protocol Synthetic environment law and sample The confirmatory sample contains 128 i.i.d. synthetic cloud environments drawn from the registered law Psyn . Each supplies four paired contexts: horizons 8 and 24 crossed with moderate and strong residual correlation. Within a cell, roles are disjoint: Fit 128, Build 512, Screen 512, Certification 8192, and Evaluation 512. Build and Screen are each divided 256/256. All methods share banks, scene order, common random numbers, endpoint definitions, and action replays. The population law is explicit. For VM i, draw bi ∼ U [.15, .23], ai ∼ U [.03, .09], a phase-group center, a normal phase perturbation, a Rademacher loading ri , and a normal scale perturbation zi . The same environment draws are reused in its four contexts. With circular dis-
tance dH , set pit = exp{− 21 [dH (t, ϕi )/1.10]2 }, µit = clip[0,.92] (bi + ai pit ), ϕi = (ζg(i) + 3ϵi ) mod H, ℓi = (.35 + .65ri )si , si = clip[.35,2.5] {exp(.6zi − .18)}.
(22)
For scene s, √ the common factor follows us,t = .55us,t−1 + 1 − .552 ξs,t . With independent standardnormal phase-bin shock G and idiosyncratic shock E, p Ms,i,t = γℓi us,t + 1 − .652 Gs,round(ϕi ),t (23) + .65Es,i,t + .12 sin{2π(t − ϕi )/H}, where γ ∈ {.40, .80}. The realized load is Ys,i,t = clip[0,1.35] {µit +.045Ms,i,t /Di }; Di is the square root of the population random-factor variance plus sinusoid time variance, lower-bounded by .25. Independent, named pseudorandom substreams determine environment, context, role, and panel identities; outcome streams do not depend on action identifiers or analysis results.
Frozen incumbent and baseline roster Development-B freezes the 40-cell scale-free full-leximin winner described in the incumbent-construction procedure above. Its direct H0 − 1 algorithm action, not a release-or-H0 row, is the formal comparator construction. Within the first nonempty generator result, the exact projected-certificate key reranks actions and chooses π I before CARA Search. The resulting comparator is therefore a certificate-reranked frozen-generator incumbent, not a verbatim deployment of an off-the-shelf heuristic. The roster consists of: • Global96: 96 fixed/randomized FFD orders, common covariance feasibility, and complete replay; • ProjBlind-2H: the same incumbent-augmented problem, ordered seeds, two-host blocks, complete action universe, m, P , and deduplication as CARA, but a
Quantity
Value
Quantity
Value
VMs / horizons Base / peak amplitude Residual scale / AR(1) Scale heterogeneity Fit / Build / Screen Build / Screen split κ / tolerance Search caps
100 / {8, 24} [.15, .23] / [.03, .09] .045/.55 .60, clip [.35, 2.5] 128/512/512 256 + 256/256 + 256 .01/10−12 2,000,000 nodes
Correlation strength Phase dispersion / width Idiosyncratic weight Capacity / load clip Certification / Evaluation Model z / shrinkage Search m, P / Cover K Bound-call cap
.40, .80 3.0/1.10 .65 1/[0, 1.35] 8192/512 1.2815515655/.10 8, 16/4 2,000,000
Table 4: Registered generator, bank, and search constants. Intervals are population support, not method-specific tuning ranges. Generator Verified evacuation ProjBlind-2H Global96 ILS ALNS
Eligible / 40
Roster position
38 35 35 4 0
1 (selected) 2 3 4 5
Table 5: Complete Development-B comparator freeze. Eligibility is the first selection key; full leximin of the direct-Evaluation ranks completes the frozen rule. fixed unprojected directional-mass order; the incumbent is excluded before deduplication/top-P , and plans are attached relative to the same anchor only after structural ranking; • verified donor evacuation with exact H0 − 1 output; and • prospectively budgeted ILS and ALNS with relocate, swap, and bounded exchange neighborhoods (Fleszar and Hindi 2002; Alvim et al. 2004; Lourenço, Martin, and Stützle 2003; Ropke and Pisinger 2006; Pisinger and Ropke 2019). All generators obey the same capacity/covariance checks and consume the same role-separated data. Their methodspecific node, replay, move, and wall-time caps are fixed prospectively; we do not call unlike work units “matched”. Timeouts and empty sets remain visible. The central mechanism comparison is CARA versus ProjBlind-2H, since it changes the certificate coordinates while holding the physical search class fixed.
Confirmatory estimand and decision rule M Let Ypcie be endpoint e for environment p, context c, scene i, and terminal policy M . For each p, average the paired CARA-minus-incumbent difference over all four contexts and Evaluation scenes; call this cluster difference ∆pe . A one-sided Student upper endpoint U.95,e is formed from the 128 environment differences. Let Tpe = 1{∆pe ̸= 0} and Bpe = 1{∆ P pe < 0}, where P negative favors CARA. Write Ne = p Tpe , Se = p Tpe Bpe , n− e = Se , and + ne = Ne − Se . The sign p-value is
psign = Pr{Bin(Ne , 1/2) ≥ Se }, e
(24)
with value one when Ne = 0. Advancement requires 1. U.95,e < 0 and psign ≤ .05 for every e ∈ e {J, V, R, S, raw}; and
2. ∆J ≤ −1/200. Proposition 4 (tie-conditional provider sign calibration). Condition on the full tie vector Te = (T1e , . . . , T128,e ). If the active signs are conditionally independent and Pr{Bpe = 1 | Te } ≤ 1/2 for every p with Tpe = 1, (25) then Eq. (24) is super-uniform. At the boundary where every active probability is 1/2, the conditional count has the exact finite-sample binomial law (with the usual discreteness). In particular, i.i.d. draws from Psyn satisfy this premise under the provider-level null PrPsyn (∆e < 0 | ∆e ̸= 0) ≤ 1/2. Proof. Given Te , couple each active Bpe to an independent fair Bernoulli using a common uniform. Under Eq. (25), their sum is no larger almost surely than the fair-binomial sum, so its upper tail is conservative. Equality of every active success probability gives the exact fair-binomial law. □ The J magnitude gate is an observed-effect safeguard, not a confidence statement that the population effect exceeds .005. The two inferential components deliberately address different failures: the Student gate requires a negative population mean, while the sign gate requires improvements to outnumber worsenings among non-tied environments. A few large gains therefore cannot mask widespread small regressions, and many tiny gains cannot mask a large mean regression. Each component uses the full one-sided .05 level inside one intersection–union claim; no multiplicity division is needed for the global conjunction. The Student statement is finite-sample exact under i.i.d. normal cluster differences and otherwise uses the conventional large-sample approximation for the mean. Proposition 4 concerns the tie-conditional probability of a negative cluster difference; it does not by itself imply negative mean effect or an unconditional improvement probability. Bootstrap and sign-flip summaries are sensitivities. Both assignments are recounted against the precommitted cell target: H0 − 1 for an available incumbent or H0 for a structural exact-zero cell. Thus H is a structural equality, not a statistical endpoint. The intention-to-treat estimand includes every ordinary fallback as a zero difference from π I . Search, noalarm, release, and fallback rates remain mechanism summaries. Conditioning on released cells would answer a different, selected question and is not used for advancement.
Prospective Design Checks Two outcome-free calculations answer different design questions. First, the Certification sizing study fixes an action and plans that have already reached Certification. A preliminary nC = 4096 candidate did not meet the prespecified joint lower-bound target. For the selected nC = 8192, 100,000 Monte Carlo trials gave joint fourcomponent pass probability .83147, a direct 99% lower bound of .82870, and a dependence-free union lower bound of .81480; all exceed .80. This calculation determines only nC and excludes Search, Route, e-Guard admission, release rate, and the environment-level primary analysis. Second, the environment-count calculation is an outcome-free analytic sensitivity for the 11 registered events: five zero-margin Student superiority gates, five exact sign-dominance gates, and the J observed-effect safeguard. For the Student calculation it assumes 128 independent, approximately normal cluster differences. For each sign calculation it assumes Pr(∆e < 0) = .20, Pr(∆e > 0) = .02, and tie probability .78. The individual model powers are replayed exactly from the registered binary64 values below. Applying the union bound to those 11 values, without assuming independence among decision indicators, gives a joint lower bound of .939247, above the prospective .80 target. At the listed variance envelopes every Student gate has standardized effect .363055 and noncentral-t power .992669. Each exact sign gate has power .999180 under the stated three-cell model. For J alone, the safeguard ∆J ≤ −.005 has standardized gap .181527 and normalmodel power .98. No environment-power simulation was run, and this calculation makes no claim about realized variance or achieved power. Computational feasibility is assessed separately. Exhaustive small instances must agree with pruned Search under both structural-reference and explicit incumbent anchors. A Fit-selected stress grid records the complete unpruned inventory, visited and pruned nodes, exact plan fits, physical replays, cap status, wall time, and peak memory. These measurements support implementation feasibility; they do not alter the statistical gate or imply a runtime bound over all cloud instances. All registered experiments and validation checks are CPU-only on an x86-64 Ubuntu 22.04.5 host exposing two 28-core Intel Xeon Platinum 8362 sockets (112 logical CPUs) and 935 GiB RAM. Experiment processes pin OpenMP, OpenBLAS, and MKL to one thread; at most three formal cells run in parallel. The locked environment is CPython 3.12.13 with NumPy 2.5.1, SciPy 1.18.0, pandas 3.0.3, scikit-learn 1.9.0, PyArrow 25.0.0, and matplotlib 3.11.0. No GPU is used.
Complete Results All result blocks are derived from the same locked analysis specification and complete 512-cell record. They include all 128 environments, four contexts, five primary endpoints, structural host checks, and every fallback. Analysis proceeds only after verifying cell completeness, comparator and anchor identity, and all required result
H=8, moderate H=8, strong H=24, moderate H=24, strong U. 95
Overall (registered) −0.06
−0.04
−0.02
0.00
ΔJ: CARA - selected comparator (lower is better)
Figure 1: Environment-level ∆J for CARA minus the frozen incumbent policy; lower is better. Context rows use descriptive two-sided 95% Student intervals. The overall row first averages the four contexts within environment and shows the registered one-sided confidence set (−∞, U.95 ]. Vertical lines mark zero and the separate observed-effect safeguard −.005. fields. Severity endpoint audit. S = min{raw/.01, 1} and raw severity were both retained because the latter audits the bounded proxy used by the registered rule. They should not be read as empirically independent dimensions: among 262,144 Evaluation scenes per policy, S saturated in 4 scenes for CARA, 9 for the incumbent, and 5 for ProjBlind-2H; the corresponding Pearson correlations between S and raw were .999907, .999821, and .999912. This complete post-outcome diagnostic leaves the registered five-endpoint analysis intact.
Post-outcome context robustness audit Table reports the complete fixed 4 × 5 context–endpoint roster, rather than selecting the largest effects. This family was constructed after outcomes were available and is descriptive only: it cannot replace, strengthen, or reverse the registered environment-cluster-averaged confirmatory decision. Each of its 20 point estimates and simultaneous one-sided upper endpoints is below zero. This is not a claim that every synthetic environment improved: for J, the four context-wise (n− , n+ , n0 ) counts are (113, 2, 13), (112, 0, 16), (98, 2, 28), and (102, 3, 23); the continuous endpoints have no positive environment difference but retain ties.
Mechanism comparisons and stage flow The complete fixed-policy audit in Table separates two findings that a single aggregate rank would conceal. Relative to Global96, ILS, and ALNS, all 15 endpoint means and simultaneous upper endpoints favor CARA, and every environment-level difference is negative (128/128 for each contrast). The matched ProjBlind-2H result goes the other way: all five point estimates are slightly positive, and none of the one-sided simultaneous sets excludes zero in favor of CARA. Thus these data do not show that certificate ordering improves terminal outcomes over the
Design
Trials
J
V
R
S Joint criterion
Candidate nC = 4096 10,000 .9776 .9249 .9294 .9281 Below target (joint bounds .7701/.7376) Selected nC = 8192 100,000 .99984 .94015 .94146 .93989 Meets target (joint .83147; bounds .82870/.81480)
Table 6: Prospective Certification-component sizing. “Joint” is the empirical four-component pass probability for a fixed action and plans. Endpoint Model mean J V R S Raw
Max. SD Mean power p− p+ Sign power
−.010 .0275440 −.004 .0110176 −.001 .00275440 −.010 .0275440 −.00010 .000275440
.992669 .992669 .992669 .992669 .992669
.20 .20 .20 .20 .20
.02 .02 .02 .02 .02
.999180 .999180 .999180 .999180 .999180
Table 7: Registered n = 128 design sensitivity for the 11 decision events. Each endpoint contributes a zero-margin Student gate and an exact sign gate; only J adds the observed-effect safeguard. Powers are model based, not realized. matched structural order; no equivalence or noninferiority margin was registered. The entire 20-member audit is post-outcome descriptive and cannot override the confirmatory comparison with the frozen incumbent. The CARA and ProjBlind-2H algorithms, common action universe, data roles, and direct paired terminal estimand were frozen before formal outcomes. The comparison uses the same incumbent-augmented problem, seed inventory, eligible blocks, m, and P ; it is not the difference of two incumbent-relative summaries and does not filter unreleased cells. No separate mechanism superiority or equivalence gate was registered, so its statistical contrasts are post-outcome descriptive and do not enter the advancement claim. When ProjBlind-2H is the frozen direct incumbent row, the numeric table is retained but marked primary/direct rather than an active mechanism comparison. Across the 512 matched cells, the two policies ended at the same physical action in 328 cells and at different actions in 184. Among 442 common-release cells, 267 had the same action and 175 had different actions; three cells released only CARA, six released only ProjBlind2H, and 61 released neither. Table retains the complete execution totals. Runtime is deliberately omitted because the stored timer scopes and provenance differ. Nodes and bound evaluations are also algorithm-specific counters, not comparable work units; their raw values support auditability but no speed, cost-ratio, or efficiency claim. The implemented computation ablation disables pruning while retaining exhaustive leaf ranking; its ordered top-P prefix must equal pruned Search whenever neither cap binds. Small instances additionally use an independent exhaustive action-universe oracle.
Prospectively frozen shifted-Evaluation stress test On fresh Evaluation banks under the prospectively frozen 0.35 deployment shift, the already committed CARA terminal action passed both the one-sided mean and exact non-tie sign components for all five endpoints across 128 synthetic environment clusters (512 repeatedcontext cells). This is terminal-action robustness evidence only; it neither reruns nor validates the end-to-end OOD
selection-and-release pipeline. The stress law changes only the fresh Evaluation innovations through the registered deployment shift of 0.35. It preserves the 128 latent synthetic environments and replays the two already committed terminal assignments; Fit, Search, Guard, Certification, selection, and release are not rerun. Thus it is neither a new provider-population sample nor an end-toend OOD policy test. The primary unit remains the synthetic environment after averaging its four repeated contexts. The complete context table is diagnostic: J is tied for all 128 environments at H = 24 under moderate correlation, while only three non-tied differences occur under strong correlation. Their component failures are retained and cannot be hidden by the environment-cluster-averaged joint pass.
Public-trace case studies We treat one trace family from each of Azure, Google, and Huawei as a named case study (Verma et al. 2015; Cortez et al. 2017; Zhang et al. 2026). Dependent windows do not create more provider labels, so no provider-population p-value is reported. Trace-specific episode construction, block intervals, complete endpoint vectors, incumbent identity, terminal counts, and structural host equality are shown without pooling them with the synthetic confirmation. The public protocol fixes four traces (Azure, two Google Borg traces, and Huawei), 48 VMs, horizon H = 8, and latest origin 528. Eligible VMs have published row length at least 536; among them, the cohort is the 48 largest 24-hour means immediately before Fit, with item identity and row index as deterministic tie breakers. Relative to each origin, the disjoint intervals are Fit [−288, −224), Search [−224, −160), Cover [−160, −128), Route [−128, −96), Guard [−96, −64), short screen [−64, 0), and the unopened Evaluation block [0, 8). The primary analysis uses origin 528. Origins 336, 384, 432, and 480 form an explicitly dependent, 48-hourstride rolling sensitivity; they are not four new providers or independent replications. For each trace–origin cell, the frozen fallback roster selects the first eligible H0 − 1 action before any CARA Search. The record fixes the actual generator, canoni-
Endpoint
Mode
Null
J V R S Raw severity
Superiority Superiority Superiority Superiority Superiority
CARA Frozen inc.
0 0.9323 0 0.1506 0 0.0132 0 0.0471 0 0.000471
∆
U.95
0.9679 -0.0357 -0.0324 0.1915 -0.0409 -0.0383 0.0171 -0.0040 -0.0037 0.0656 -0.0185 -0.0174 0.000656 -0.000185 -0.000174
pt n− /n+ /n0 ps < .0001 < .0001 < .0001 < .0001 < .0001
128/0/0 128/0/0 128/0/0 128/0/0 128/0/0
< .0001 < .0001 < .0001 < .0001 < .0001
Gate Pass Pass Pass Pass Pass
Table 8: Complete registered incumbent-relative inference. Lower is better. Every endpoint requires a zero-margin one-sided mean-superiority bound and an exact sign-dominance test; the J row also includes the observed −.005 safeguard. Hosts are excluded because exact per-scene equality is a construction invariant. Context H = 8, moderate H = 8, strong H = 24, moderate H = 24, strong
J −.04506 [−.03439] −.05501 [−.04245] −.01656 [−.01147] −.02605 [−.01858]
V −.02170 [−.01780] −.02380 [−.01944] −.05782 [−.04842] −.06039 [−.05004]
R −.003578 [−.002936] −.003990 [−.003266] −.004145 [−.003470] −.004134 [−.003432]
S −.01855 [−.01531] −.01977 [−.01617] −.01806 [−.01514] −.01758 [−.01459]
Raw −4
−1.8553×10 [−1.5310×10−4 ] −1.9781×10−4 [−1.6176×10−4 ] −1.8059×10−4 [−1.5136×10−4 ] −1.7581×10−4 [−1.4585×10−4 ]
Table 9: Complete post-outcome descriptive context audit for CARA minus the frozen incumbent (lower is better; 128 b [U ], where U is the Bonferroni synthetic environment clusters and 512 Evaluation panels per cell). Each entry is ∆ simultaneous one-sided Student upper endpoint for the fixed family of 20 context–endpoint contrasts (familywise coverage at least 95%). This audit cannot override the confirmatory decision. cal physical action, fallback path, protocol, and structural problem. Search then uses an active problem that includes this incumbent when it is not already a structural seed. Consequently, every comparison uses a neighborhood anchored to the actual incumbent rather than to a generatorspecific surrogate. The tables report the generator used to construct that incumbent. This is a shortened descriptive case-study protocol, not a second execution of the formal experiment. Its projected Search plans and held-out screen use nC = 8 paired blocks, P = 16, and registered node and boundevaluation caps of 5 × 105 . The frozen comparator roster remains the Development-B roster, but a fallback cell is named by its actual generator (for example, “ProjBlindled frozen roster”), not presented as a pure standalone ProjBlind run. Neither the eight-pair screen nor its rolling sensitivity inherits Theorem 2, a confidence statement, or provider-population scope. Coverage funnel and dependence boundary. The complete coverage funnel is 20 Search attempts → 5 candidate-bearing episodes → 3 episodes entering the short screen → 0 releases. Specifically, 15 searches completed with no eligible block; all five candidate-bearing episodes were from Borg-d, two passed e-Guard but failed the raw-direction gate, and every J/V /R/S screen component failed in each of the remaining 3 episodes. All 20 searches completed within the registered 500,000-node and 500,000-bound-evaluation caps; the largest recorded node count was 185,955. The rolling cases remain dependent sensitivity cases: within each trace their Evaluation windows are pairwise disjoint, but the 288-time-point histories at a 48-time-point stride overlap by 240 adjacent time points (144 common to all four histories), and the frozen cohorts share 43–48 of 48 items pairwise. No independent-replicate or provider-population inference is made. Tables and report every CARA trace– origin outcome. Incumbent rows are omitted because all incumbent-relative differences are identically zero by
construction.
A complete post-hoc geometry audit explains all 15 empty searches. Each 48-VM incumbent placed exactly six VMs on each of eight hosts; every two-host union therefore contained 12 VMs and exceeded the registered m ≤ 8 action class. The five Borg-d attempts instead contained 50–2,194 eligible blocks, returned the full top16, and visited 1,956–185,955 nodes. This identifies a fixed-neighborhood coverage boundary; it is not a posthoc efficacy result.
Integrity and Robustness Checks
Robustness-check matrix. Every integrity failure is handled fail-closed: it cannot produce a nominal candidate or statistical pass. The matrix below summarizes the principal perturbations and independent validation checks.
Endpoint
Mode
J V R S Raw severity
Superiority Superiority Superiority Superiority Superiority
∆
Null
U.95
0 +0.0003 +0.0007 0 +0.0005 +0.0009 0 +0.0001 +0.0001 0 +0.0003 +0.0004 0 +0.000003 +0.000004
pt ps 0.9211 0.9834 0.9957 0.9967 0.9967
Numerical rule
0.9637 1.0000 1.0000 1.0000 1.0000
Fail Fail Fail Fail Fail
Table 10: Descriptive paired CARA minus ProjBlind-2H Evaluation contrast on all five endpoints. This is computed from the two terminal rows themselves, not by subtracting incumbent-relative summaries. The numerical all-five rule failed descriptively; exact host equality held. This contrast was not separately gatekept and is not a confirmatory mechanism claim. J
V
R
S
0.9323 0.9464 0.9320 0.9679 0.9651 0.9679
0.1506 0.1612 0.1500 0.1915 0.1907 0.1915
0.0132 0.0144 0.0131 0.0171 0.0170 0.0171
0.0471 0.0530 0.0468 0.0656 0.0649 0.0656
Method CARA Global96 ProjBlind-2H Frozen incumbent policy ILS ALNS
Raw Hosts 0.000471 0.000530 0.000468 0.000656 0.000649 0.000656
26.63 26.63 26.63 26.63 26.63 26.63
Table 11: Complete intention-to-treat Evaluation means for all six frozen policies. No policy or endpoint is selected for display.
Boundary
Perturbation
Required response / validation
Late selection, incorrect H0 anchor, changed generator order, or action mismatch
Reject before Search; verify temporal order, exact H0 − 1 host count, and canonical action identity Search Non-optimistic bound, Reject on disagreement with equality pruning, changed exhaustive enumeration; anchor, or duplicate action compare pruning on and off Arithmetic Near-2−40 boundary, stale Refine outward or reject; plan, or nonpositive factor compare with rational and high-precision calculations Data Wrong role, order, count, or Reject before use; reconstruct separation shared outcome storage bank identities from the prespecified split Guard / Candidate retry, changed Veto or invalidate the family; Certification threshold, premature access, independently recompute or bank reopening exact test statistics and one-use access order Formal Missing row, duplicate Reject; independently analysis environment, changed aggregate outcomes and mean/sign gate, or host-count recount structural substitution assignments Incumbent
At each stage, inputs are treated as immutable and bound to their data role, scene order, endpoint definitions, and action/incumbent identities. Search checks include zero Build differences, lattice ties, duplicate origins, an incumbent inside the enumerated leaves, and work-cap precedence. Statistical checks include all-zero environment differences, constant favorable differences, missing conditions, endpoint reordering, and exact equality at every decision threshold. A provenance record links the prespecified analysis, bank-opening sequence, terminal decisions, Evaluation rows, and reported tables. Independent recomputation verifies one-use data access and complete policy-family accounting. These checks make data reuse, action substitution, and silent omission detectable; they do not estab-
lish the scientific sampling assumptions.
Additional Limitations and Deployment Notes The paired-sign assumption for J is substantive. A common latent shock across Certification rows can preserve a marginal mean while invalidating the fair-sign argument. Likewise, the independent-average continuous proof path cannot be combined with serial dependence, and the sequential path cannot hide positive conditional means behind later compensation. Immutable commitment records verify information flow, not exchangeability or stationarity. The study models a static homogeneous-host decision. Migration cost, arrivals and departures, multi-resource interference, heterogeneous hardware, priority classes, and delayed feedback lie outside its scope. Scenario and robust optimization offer complementary approaches to distributional uncertainty (Charnes and Cooper 1959; Nemirovski and Shapiro 2007; Calafiore and Campi 2006; Campi and Garatti 2008; Luedtke and Ahmed 2008; Pagnoncelli, Ahmed, and Shapiro 2009; Campi, Garatti, and Ramponi 2018; Hadj Salem, Silva, and Oliveira 2023; Bougeret et al. 2022). Deployment would require a prospective refresh schedule and a separate drift alarm. The e-Guard is not that alarm: it controls false veto under bounded no-harm nulls but offers no false-nonveto guarantee. Finally, nC = 8192 increases latency and is appropriate only when independent replay is cheaper than an unsafe change and the incumbent is a meaningful fallback. The sizing calculation assumes its variance envelope; it implies neither free samples nor frequent Guard admission.
Method
Search Raw pass No alarm
CARA 469/512 Global96 404/512 ProjBlind-2H 468/512 Frozen incumbent policy 0/512 ILS 28/512 ALNS 0/512
469/512 359/512 468/512 0/512 27/512 0/512
Cert. Release Fallback Cand./cell
469/512 445/469 445/512 67/512 353/512 281/353 281/512 231/512 468/512 448/468 448/512 64/512 0/512 – 0/512 40/512 27/512 17/27 17/512 495/512 0/512 – 0/512 512/512
Nodes
Bounds
14.66 32944186 28086939 7.35 48864 6301 14.62 32644608 114094 0.00 17701735 862 0.88 2623124 594109 0.00 810300 356891
Table 12: Complete stage flow over all 512 formal cells. A precommitted recovery procedure assigned the fixed reference action to all policies in 3 cell(s); 40 cell(s) used the preregistered structural-H0 ITT zero rule. Both statuses remain visible. In available-incumbent cells the selected reference row is direct deployment and has no Search, raw-direction, Guard, or Certification operation; structural cells retain their generator terminal and reference fallback. Dashes denote inapplicability.
J
Comparator
V
R
S
Raw −5
Global96 −.01416 [−.01169] −.01065 [−.009351] −.001252 [−.001106] −.005891 [−.005132] −5.8923×10 [−5.1329×10−5 ] ILS −.03286 [−.02712] −.04018 [−.03572] −.003838 [−.003427] −.01781 [−.01593] −1.7815×10−4 [−1.5929×10−4 ] ALNS −.03567 [−.03007] −.04092 [−.03645] −.003962 [−.003553] −.01849 [−.01662] −1.8493×10−4 [−1.6623×10−4 ] ProjBlind-2H +.000313 [+.000942] +.000522 [+.001215] +5.1796×10−5 [+1.0728×10−4 ] +.000254 [+.000517] +2.5405×10−6 [+5.1730×10−6 ]
Table 13: Complete post-outcome descriptive secondary-policy audit, averaged over the four fixed contexts (CARA minus policy; lower is better; 128 synthetic environment clusters and 2,048 paired Evaluation panels per environment). b [U ] for a fixed 20-contrast Bonferroni family with simultaneous one-sided coverage at least 95%. The Entries are ∆ table cannot override the confirmatory decision.
Policy
Search complete
Candidates
Visited nodes
Bound evals.
Released
Fallback
469 468
7,504 7,488
32,944,186 32,644,608
28,086,939 114,094
445 448
67 64
CARA ProjBlind-2H
Table 14: Post-outcome descriptive execution accounting for the same fixed incumbent-augmented neighborhoods (512 cells). Candidate, node, and bound counts are raw policy-specific audit counters; neither these counters nor the incomparably timed runtimes support a cross-policy cost ratio. “Fallback” is the committed-reference terminal.
Endpoint J V R S Raw
CARA Frozen inc. 0.9968 0.3877 0.0406 0.2211 0.002224
0.9985 0.4166 0.0470 0.2714 0.002734
∆ −0.0017 −0.0289 −0.0063 −0.0503 −0.0005
U.99 n− /n+ /n0 −0.0013 −0.0261 −0.0058 −0.0461 −0.0005
99/11/18 128/0/0 128/0/0 128/0/0 128/0/0
ps Gate < .0001 < .0001 < .0001 < .0001 < .0001
Pass Pass Pass Pass Pass
Table 15: Prospectively frozen terminal-action stress test under the registered 0.35 deployment shift (CARA minus frozen incumbent; lower is better; 128 synthetic environment clusters and 512 repeated-context cells). Each primary endpoint uses component α = .01; the joint screen passes only if every one-sided Student upper endpoint is below zero and every exact non-tie sign test passes. This is not an end-to-end OOD policy experiment.
J
V
R
S
Raw
H = 8, moderate −0.0025 [−0.0015] H = 8, strong −0.0043 [−0.0025] H = 24, moderate 0 [0] H = 24, strong −7.63×10−5 [6.76×10−5 ]
−0.0229 [−0.0187] −0.0262 [−0.0212] −0.0267 [−0.0213] −0.0399 [−0.0322]
−0.0051 [−0.0042] −0.0060 [−0.0049] −0.0068 [−0.0057] −0.0074 [−0.0062]
−0.0455 [−0.0376] −0.0499 [−0.0408] −0.0510 [−0.0428] −0.0547 [−0.0454]
−0.0005 [−0.0004] −0.0005 [−0.0004] −0.0005 [−0.0004] −0.0005 [−0.0005]
Context
b [U ] in one fixed 20Table 16: Complete context diagnostics for the frozen terminal-action stress test. Entries are ∆ member Bonferroni family. These repeated-context rows cannot replace or rescue the synthetic-environment-averaged primary screen.
Trace Origin Incumbent source Azure Borg-d Borg-e Huawei
528 528 528 528
Verified evacuation Verified evacuation Verified evacuation Verified evacuation
Terminal state
∆J
∆V
∆R
∆S
No candidate Guard veto No candidate No candidate
+0.000 +0.000 +0.000 +0.000
+0.00000 +0.00000 +0.00000 +0.00000
+0.00000 +0.00000 +0.00000 +0.00000
+0.00000 +0.00000 +0.00000 +0.00000
∆Raw ∆H +0.00000 +0.00000 +0.00000 +0.00000
+0 +0 +0 +0
Table 17: Public-trace outcomes for one role-disjoint primary episode per trace. Lower is better. The incumbent source identifies the generator used by the frozen roster. All CARA trace outcomes and endpoint differences are shown; the omitted incumbent rows are zero by construction. These named cases support no provider-population inference.
Trace Origin Incumbent source Azure Azure Azure Azure Borg-d Borg-d Borg-d Borg-d Borg-e Borg-e Borg-e Borg-e Huawei Huawei Huawei Huawei
336 384 432 480 336 384 432 480 336 384 432 480 336 384 432 480
Verified evacuation Global96 Verified evacuation Global96 Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation Verified evacuation
Terminal state
∆J
∆V
∆R
∆S
No candidate No candidate No candidate No candidate Guard veto Screen failure Screen failure Screen failure No candidate No candidate No candidate No candidate No candidate No candidate No candidate No candidate
+0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000 +0.000
+0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000
+0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000
+0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000
∆Raw ∆H +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000 +0.00000
+0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0 +0
Table 18: Public-trace outcomes for the four dependent rolling-history origins per trace. Lower is better. All CARA trace–origin outcomes are retained; omitted incumbent rows are zero by construction. The rolling origins are sensitivity cases, not independent replications.
References Alvim, A. C. F.; Ribeiro, C. C.; Glover, F.; and Aloise, D. J. 2004. A Hybrid Improvement Heuristic for the OneDimensional Bin Packing Problem. Journal of Heuristics, 10(2): 205–229.
Bougeret, M.; Dósa, G.; Goldberg, N.; and Poss, M. 2022. Constant-Ratio Approximation for Robust Bin Packing with Budgeted Uncertainty. SIAM Journal on Discrete Mathematics, 36(4): 2534–2552.
Calafiore, G. C.; and Campi, M. C. 2006. The Scenario Approach to Robust Control Design. IEEE Transactions on Automatic Control, 51(5): 742–753.
Campi, M. C.; and Garatti, S. 2008. The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs. SIAM Journal on Optimization, 19(3): 1211–1230.
Campi, M. C.; Garatti, S.; and Ramponi, F. A. 2018. A General Scenario Theory for Nonconvex Optimization and Decision Making. IEEE Transactions on Automatic Control, 63(12): 4067–4078.
Charnes, A.; and Cooper, W. W. 1959. ChanceConstrained Programming. Management Science, 6(1): 73–79.
Coffman, E. G.; Garey, M. R.; and Johnson, D. S. 1996. Approximation Algorithms for Bin Packing: A Survey. In Hochbaum, D. S., ed., Approximation Algorithms for NP-Hard Problems, 46–93. PWS Publishing.
Cortez, E.; Bonde, A.; Muzio, A.; Russinovich, M.; Fontoura, M.; and Bianchini, R. 2017. Resource Central: Understanding and Predicting Workloads for Improved Resource Management in Large Cloud Platforms. In Proceedings of the 26th ACM Symposium on Operating Systems Principles, 153–167.
Fleszar, K.; and Hindi, K. S. 2002. New Heuristics for One-Dimensional Bin-Packing. Computers & Operations Research, 29(7): 821–839. Hadj Salem, K.; Silva, E.; and Oliveira, J. F. 2023. Cutting and Packing Problems under Uncertainty: Literature Review and Classification Framework. International Transactions in Operational Research, 30(6): 3329–3360. Lourenço, H. R.; Martin, O. C.; and Stützle, T. 2003. Iterated Local Search. In Glover, F.; and Kochenberger, G. A., eds., Handbook of Metaheuristics, volume 57 of International Series in Operations Research & Management Science, 320–353. Springer. Luedtke, J.; and Ahmed, S. 2008. A Sample Approximation Approach for Optimization with Probabilistic Constraints. SIAM Journal on Optimization, 19(2): 674–699. Murty, K. G. 1968. Letter to the Editor—An Algorithm for Ranking All the Assignments in Order of Increasing Cost. Operations Research, 16(3): 682–687. Nemirovski, A.; and Shapiro, A. 2007. Convex Approximations of Chance Constrained Programs. SIAM Journal on Optimization, 17(4): 969–996. Pagnoncelli, B. K.; Ahmed, S.; and Shapiro, A. 2009. Sample Average Approximation Method for Chance Constrained Programming: Theory and Applications. Journal of Optimization Theory and Applications, 142: 399–416. Pisinger, D.; and Ropke, S. 2019. Large Neighborhood Search. In Gendreau, M.; and Potvin, J.-Y., eds., Handbook of Metaheuristics, volume 272 of International Series in Operations Research & Management Science, 99– 127. Springer, 3 edition. Przybylski, A.; and Gandibleux, X. 2017. MultiObjective Branch and Bound. European Journal of Operational Research, 260(3): 856–872. Ramdas, A.; Grünwald, P.; Vovk, V.; and Shafer, G. 2023. Game-Theoretic Statistics and Safe Anytime-Valid Inference. Statistical Science, 38(4): 576–601. Ropke, S.; and Pisinger, D. 2006. An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4): 455–472. Scholl, A.; Klein, R.; and Jürgens, C. 1997. BISON: A Fast Hybrid Procedure for Exactly Solving the OneDimensional Bin Packing Problem. Computers & Operations Research, 24(7): 627–645. Shafer, G.; Shen, A.; Vereshchagin, N.; and Vovk, V. 2011. Test Martingales, Bayes Factors and p-Values. Statistical Science, 26(1): 84–101. Verma, A.; Pedrosa, L.; Korupolu, M.; Oppenheimer, D.; Tune, E.; and Wilkes, J. 2015. Large-Scale Cluster Management at Google with Borg. In Proceedings of the Tenth European Conference on Computer Systems, 1–17. Zhang, X.; Shen, L.; Chen, M.; Li, Z.; Li, H.; Fu, H.; Sun, J.; Ren, X.; and Liu, C. 2026. CloudCons: A Comprehensive End-to-End Benchmark for Cloud Resource Consolidation. ArXiv preprint, arXiv:2606.13513.