{"id":"1d8aa9a0-89bc-4a17-a473-ed6c14af59fa","arxiv_id":"2412.11447","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"DeDe uses ADMM-style variable splitting to decompose separable resource allocation problems into per-resource and per-demand subproblems, cutting solve times by 2-8x in three cloud workloads.","lead":"DeDe is a new software framework that solves huge cloud resource allocation problems by splitting them into many small pieces that a computer can work through in parallel. It reports 2 to 8 times faster solutions than existing approaches while keeping allocation quality close to optimal.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Load-bearing concern: DeDe's integer/nonconvex extension (Sec. 4.1) rests on an unproven ADMM projection; the load-balancing formulation is incomplete and the 'no compromise in solution quality' claim is unsupported.","rationale":"The convex continuous core of DeDe (Sec. 3) is theoretically sound: two-block ADMM converges for convex problems, and the decomposition into per-resource and per-demand subproblems is valid. The central claim, however, extends to the full separable class in Eqs. (1)-(3), which Table 1 shows includes boolean and integer variables. The weakest link is the handling of these discrete variables: the paper provides no convergence theorem, the cited references do not apply directly to the mixed-integer subproblems produced by Eqs. (8)-(9), and the load-balancing case study contains an apparent omitted linking constraint, making its empirical claims unreliable. This matches the reader's identified weakest assumption. The concern does not invalidate the convex contribution, but it does mean the paper's headline claims of generality and no quality compromise overreach. A conditional acceptance requiring the authors to either prove or empirically validate the integer case, and to correct the load-balancing formulation, is appropriate. Hence the reader's CONDITIONAL verdict stands unchanged.","tokens_in":21922,"tokens_out":9328,"duration_ms":80671,"concrete_test":"Use the released pip package to run DeDe on small random load-balancing instances (e.g., n=8 servers, m=16 shards) for which the true MILP optimum can be computed exactly with Gurobi or CPLEX. Verify the implementation includes the x_ij <= x'_ij linking constraint; if absent, add it. Sweep the ADMM penalty rho over {0.1, 1, 10, 100} and compare DeDe's final objective, constraint violations, and consensus residual to the global optimum. If the optimality gap exceeds 5% or any run returns an infeasible solution, the integer/nonconvex claim in Sec. 4.1 fails and the abstract's no-compromise statement must be scoped to convex continuous problems.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (near-optimal solutions for any separable problem) requires that ADMM with integer projection converges to high-quality feasible points for the nonconvex/integer class. Section 4.1 asserts this via refs [39,57,61], but none covers two-block ADMM with mixed-integer subproblems as in Eqs. (8)-(9). In load balancing (Sec. 5.3), the x-minimization subproblem (Eq. 8) includes binary variables x' and the implicit coupling x_ij <= x'_ij, which the paper never states; without it, setting x'=0 yields objective 0 and the stated model is degenerate. With the intended constraint, each per-server subproblem is an MILP with m binary variables, and exact solution is NP-hard; nonconvex ADMM convergence results require exact subproblem solves and additional regularity conditions not established here. Section 4.2 concedes 'DEDE may fail to reach the optimal solution' for nonconvex problems, which directly contradicts the introduction's 'without compromising solution quality.' The load-balancing evaluation (Fig. 8) compares DeDe to a per-round Exact sol. that is not globally optimal over the sequence, and reports no optimality gap or constraint-violation statistics. Thus the empirical '12.6% higher quality' on load balancing cannot substantiate the general integer-class claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes DeDe, a framework for large-scale resource allocation problems that have separable objective and constraint structure. DeDe introduces an auxiliary variable z duplicating the allocation matrix x, moves demand-side constraints and objective terms onto z, and applies scaled-form ADMM to alternate between independent per-resource updates (Eq. 8) and per-demand updates (Eq. 9). The paper claims this decouple-and-decompose approach yields near-optimal solutions without compromising quality, and presents a Python package plus experiments on cluster scheduling, traffic engineering, and load balancing, reporting speedups and quality improvements over POP and other baselines.","tokens_in":22211,"tokens_out":3428,"duration_ms":33944,"significance":"For continuous convex separable problems, the ADMM-based decomposition is standard and the derivation in Section 3 is sound; the evaluation shows meaningful empirical speedups, and the public release of a working parallel implementation is a concrete systems contribution. The central weakness is that the paper extends the claim to integer and non-convex problems (load balancing) using an unproven projection heuristic, and the abstract's 'without compromising solution quality' assertion is not supported for that class. If the claims are narrowed to continuous convex problems and the integer extension is presented as a heuristic with appropriate caveats, the paper would be a useful contribution to scalable resource allocation.","major_comments":[{"comment":"The claim that DeDe 'should effectively handle boolean and integer variables by projecting real-valued solutions onto the appropriate domains' is not supported by the cited references. References [39,57,61] do not establish convergence or solution-quality guarantees for the two-block ADMM scheme in Eqs. (8)–(9) when subproblems contain mixed-integer variables, nor for the inexact subproblem solves used in practice. Section 4.2 concedes that DeDe 'may fail to reach the optimal solution' in non-convex settings, which directly conflicts with the introduction's claim of 'without compromising solution quality.' Since the load-balancing evaluation in §5.3 relies on binary variables, this gap is load-bearing and should be addressed by either restricting the generality claims or providing concrete convergence/quality analysis or substantially more evidence for the integer class.","section":"§4.1, Eqs. (8)–(9)"},{"comment":"The load-balancing formulation is incomplete and, as stated, degenerate. The continuous variables x_ij and binary variables x'_ij are not linked by any constraint such as x_ij <= x'_ij or x_ij > 0 => x'_ij = 1. Without such a coupling, the objective and memory constraints depend only on x', so setting x' = 0 is always optimal for any feasible x, and the model does not actually minimize shard movements. With the intended coupling, each per-server subproblem becomes an MILP with m binary variables, whose exact solution is NP-hard, and the paper provides no convergence or approximation guarantee for ADMM on this class. This undermines the load-balancing results in Figure 8 and the related claims of higher allocation quality.","section":"§5.3, Eq. (8)"},{"comment":"The complexity statement that decomposition reduces the original O((n m)^2.373) cost to O(n m^2.373) is explicitly conditional on ADMM 'converging within a constant number of iterations,' but no such constant-iteration bound is provided or cited for the general separable problem class. The iteration count depends on the penalty parameter rho, stopping tolerances, and problem conditioning, and these are free parameters in the implementation. The theoretical speedup claim should therefore be presented as an empirical observation, not a worst-case complexity result, or it should be backed by a convergence-rate analysis.","section":"§3.2, complexity comparison"},{"comment":"The load-balancing comparison does not substantiate the 'higher-quality allocations' claim. The 'Exact sol.' baseline solves each scheduling round independently, and the text admits it 'does not produce the minimum possible shard movements because optimizing each scheduling round independently does not guarantee an optimal solution across the entire series.' No optimality gap or constraint-violation statistics are reported for any method. Since DeDe's average of 20.1 shard movements is better than Exact sol.'s 20.9, the evaluation needs a proper sequence-level baseline or a per-round gap analysis before the quality claim can be accepted.","section":"§7.1.3 and Fig. 8"}],"minor_comments":[{"comment":"In the proportional-fairness experiment, Exact sol. is reported to fail to reach optimality even after five hours, and several methods therefore achieve normalized fairness scores above 1. The paper should clarify that the normalization baseline is not an exact optimum and should report absolute objective values or optimality gaps.","section":"§7.1.1, proportional fairness"},{"comment":"The discussion of 'limited parallelism' would benefit from a concrete example or bound quantifying how aggregation reduces parallelism, rather than only a qualitative statement.","section":"§4.2, limitations"},{"comment":"The sentence 'the objectives are expressed as either a sum over per-demand utilities or as a maximum over per-link utilities' is slightly imprecise because the maximum over link utilization is not a sum of per-link utilities; the connection to the augmented Lagrangian is clear but the wording could be tightened.","section":"§5.2, traffic engineering"},{"comment":"The comparison of DeDe and DeDe* would be easier to interpret if the paper consistently distinguished end-to-end wall-clock time from solver-only time in every figure, since DeDe* explicitly excludes compilation, solving-unpacking, and scheduling overheads.","section":"§7.1.1, cluster scheduling"}],"recommendation":"major_revision","confidential_remarks":"The core ADMM decomposition for continuous convex separable problems is standard, so the novelty rests primarily on the systems implementation and the breadth of the empirical study. The paper's most distinctive claim—general support for integer and boolean problems—is currently the least supported part of the manuscript. I would advise the editor that acceptance should hinge on the authors either restricting the scope of the claims or supplying a rigorous treatment of the integer case; the present form is not ready for publication as a general-purpose framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: read this for the convex core, not for the integer story. The decouple-and-decompose pattern — duplicate the allocation matrix as z, run two-block ADMM, decompose into per-resource and per-demand subproblems — is clean, and as far as the citations show, not done before at this level of generality. For convex continuous problems (max-min and proportional fairness as LPs, TE as LP), the Sec. 3 derivation follows standard ADMM theory and the decomposition is sound. The system contribution is also real: a pip-installable cvxpy-style package, actual Ray parallelism, and an evaluation on three canonical tasks with plausible speedups over POP. The robustness experiments against granularity, temporal, and spatial shifts are a nice counter to POP's granularity assumption.\n\nNow the soft spots. The integer/nonconvex story overreaches. Sec. 4.2 concedes DEDE may be suboptimal for non-convex problems, and the cited ADMM guarantees [39,57,61] do not cover mixed-integer two-block ADMM of the form in Eqs. (8)-(9). The load-balancing evaluation uses a binary x', so it is carrying weight the theory does not support. More concretely, Sec. 5.3 never states the constraint linking x and x' (e.g., x_ij <= x'_ij). As written, the objective only involves x', and x'=0 is a trivial optimum; the model is degenerate. 'x′ij=1 if xij>0' is a definition, not a constraint. That is a real gap and should be fixed before the load-balancing numbers are meaningful.\n\nMinor issues: rho is unreported and likely tuned; figures lack error bars; the DEDE* idealized variant appears in some headline speedups; evaluation data and scripts are not released. None of these sink the convex claim, but they matter for reproducibility.\n\nBottom line: the convex continuous decomposition is a solid contribution, and the released package lowers the adoption barrier. The paper deserves serious refereeing, and with the integer claims and load-balancing model fixed, a solid revision. The reader's conditional verdict and the stress-test concern both match my reading; the stress-test's central concern lands squarely.","headline":"The convex ADMM decomposition is a genuine contribution; the integer/nonconvex claims and the load-balancing formulation overreach.","tokens_in":22735,"tokens_out":3170,"would_cite":true,"duration_ms":27408,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DeDe splits large resource-allocation problems into many tiny parallel subproblems by decoupling resource and demand constraints, with reported near-optimal quality and large speedups.","keywords":["resource allocation","ADMM","constraint decomposition","parallel optimization","cluster scheduling","traffic engineering","load balancing","separable optimization"],"falsifier":"Run DeDe on a small mixed-integer load-balancing instance (for example, 8 servers and 16 shards) whose exact optimum can be verified by exhaustive search; if DeDe, across a sweep of the penalty parameter, returns objective values systematically worse than that known optimum on instances where the continuous relaxation is tight, the near-optimal-integer claim fails.","tokens_in":21692,"feed_emoji":"⚡","tokens_out":13055,"duration_ms":96978,"temperature":0.7,"pith_summary":"DeDe claims that most real-world resource allocation problems share a separable structure: the objective is a sum over per-resource and per-demand utilities, and every constraint applies to a single resource or a single demand. The central claim is that this structure can be exploited by a decouple-and-decompose reformulation: introduce an auxiliary copy $z$ of the allocation matrix, move demand constraints onto $z$, add $x=z$, and run ADMM. This turns one large entangled optimization into many small per-resource and per-demand subproblems that can be solved in parallel with off-the-shelf solvers, producing near-optimal allocations. If correct, DeDe is a domain-agnostic accelerator for cluster scheduling, traffic engineering, and load balancing, with reported speedups of 2.2--7.6$\\times$ and allocation-quality gains of 5.3--12.6% over the previous granular method.","feed_headline":"DeDe speeds resource allocation 2.2-7.6x over prior method","feed_subtitle":"A decouple-and-decompose method turns one giant optimization into many small parallel subproblems.","key_machinery":"The central mechanism is a two-block ADMM splitting of the allocation matrix. DeDe replaces the allocation matrix $x$ with a duplicate $z$, moves all demand constraints and demand-dependent objective terms onto $z$, and couples the blocks with $x - z = 0$. The augmented Lagrangian with penalty $\\rho$ and scaled dual variables $\\alpha$, $\\beta$, $\\lambda$ is then minimized alternately: for fixed $z$, the $x$-update separates into $n$ per-resource subproblems (Equation 8); for fixed $x$, the $z$-update separates into $m$ per-demand subproblems (Equation 9). Because every subproblem retains access to the full set of resources or demands, the decomposition does not shrink the feasible region the way subset partitioning does.","core_discovery":"The discovery is that the coupling between resource constraints and demand constraints, rather than the raw number of variables, is the main obstacle to parallelizing resource allocation. For any problem of the form $\\min \\sum_i f_i(x_{i*}) + \\sum_j g_j(x_{*j})$ subject to $R_i x_{i*} = r_i$ and $D_j x_{*j} = d_j$, DeDe duplicates the allocation matrix, rewriting the demand-side constraints and utilities on the copy $z$ while adding $x - z = 0$. The augmented Lagrangian for this equivalent problem is then minimized by ADMM: an $x$-update that separates into $n$ independent per-resource subproblems and a $z$-update that separates into $m$ independent per-demand subproblems, with multiplier updates in between. The paper argues this preserves the optimum for convex problems and, empirically, yields near-optimal allocations for the non-convex, integer load-balancing case while cutting solving time by large factors relative to exact solvers and by 2.2--7.6$\\times$ relative to the prior subset-splitting method.","pith_inferences":["If the paper's survey of separable structure generalizes, the same template should apply to other allocation settings the paper catalogues but does not evaluate, such as intercloud brokering, optical-path wavelength assignment, and electricity pricing; these are natural testbeds.","The real 64-core speedup saturates near 18$\\times$ because of cache contention and stragglers, so dynamic work-stealing or running subproblems across machines is a plausible engineering extension the paper does not pursue.","The integer-variable success is empirical; stress-testing DeDe against known-optimal mixed-integer benchmarks would map where the near-optimality claim holds and where it breaks.","Combining DeDe's decomposition with a learned coarse initializer (as the paper tests with one learning-based baseline) suggests a general recipe: leverage machine learning to propose a start and ADMM splitting to refine it."],"forward_implications":["Cluster scheduling, traffic engineering, and load balancing problems that fit the separable form can be solved in seconds rather than minutes to hours, with allocation quality at or above what exact solvers achieve within their time limits.","The number of parallel subproblems grows with the number of resources and demands, so adding CPU cores transfers to near-linear speedup until inter-process overhead and stragglers dominate.","Because each subproblem still sees all resources or all demands, DeDe's solution quality degrades far less than subset-splitting methods when demands are non-granular or resources are not interchangeable.","Warm-starting DeDe with a previously computed or learned allocation roughly halves the time to a good solution, making the method natural for repeated optimization intervals.","The decomposition is domain-agnostic: any new allocation problem expressible in the separable form can be written into the package without per-domain solver logic."],"supporting_citations":[{"why":"Supplies the ADMM alternating-direction framework and its convergence guarantee for two-block convex problems.","marker":"[8]"},{"why":"The state-of-the-art subset-splitting baseline DeDe compares against and outperforms in speed and quality.","marker":"[44]"},{"why":"The learning-accelerated traffic-engineering baseline used to show DeDe's generality and as a warm-start initializer in the convergence experiment.","marker":"[65]"},{"why":"Provides empirical evidence that ADMM iterates with projection handle mixed-integer quadratic programs.","marker":"[54]"},{"why":"One of the theoretical convergence results cited to support applying ADMM to non-convex problems.","marker":"[57]"},{"why":"One of the theoretical convergence results cited for ADMM with integer and boolean variables.","marker":"[61]"},{"why":"The convex modeling language that DeDe's user interface and subproblem construction are built on.","marker":"[15]"},{"why":"The parallel execution engine DeDe uses to run subproblems across CPU cores.","marker":"[41]"}],"fun_headline_variants":["DeDe decouples and decomposes, speeding allocation 2.2-7.6x","Turn one giant optimization into many parallel subproblems: DeDe","2.2-7.6x faster allocation via decouple-and-decompose","Decouple constraints, parallelize allocation: DeDe","Resource allocation: DeDe splits the problem into parallel parts"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For problems with whole-number or yes/no choices, DeDe assumes that repeatedly projecting ADMM's real-valued steps onto the allowed discrete values still lands near the best solution; the paper offers empirical evidence and special-case theory, but no proof for the general integer case.","fun_headline_variants_meta":{"raw":{"variants":["DeDe decouples and decomposes, speeding allocation 2.2-7.6x","Turn one giant optimization into many parallel subproblems: DeDe","2.2-7.6x faster allocation via decouple-and-decompose","Decouple constraints, parallelize allocation: DeDe","Resource allocation: DeDe splits the problem into parallel parts"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001463,"raw_usage":{"total_tokens":5902,"prompt_tokens":981,"completion_tokens":4921,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":4825}},"tokens_in":597,"tokens_out":4921,"duration_ms":32475,"temperature":1.0,"reasoning_tokens":4825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T14:55:35.956584+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DeDe on a small mixed-integer load-balancing instance (for example, 8 servers and 16 shards) whose exact optimum can be verified by exhaustive search; if DeDe, across a sweep of the penalty parameter, returns objective values systematically worse than that known optimum on instances where the continuous relaxation is tight, the near-optimal-integer claim fails.","supporting_citations":[{"cited_title":"Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.Foundations and Trends in Ma- chine learning, 3(1):1–122, 2011","cited_arxiv_id":null,"evidence_quote":"Supplies the ADMM alternating-direction framework and its convergence guarantee for two-block convex problems."},{"cited_title":"Solving Large-Scale Granular Resource Allocation Problems Efficiently with POP","cited_arxiv_id":null,"evidence_quote":"The state-of-the-art subset-splitting baseline DeDe compares against and outperforms in speed and quality."},{"cited_title":"Yan, Rachee Singh, Justin T","cited_arxiv_id":null,"evidence_quote":"The learning-accelerated traffic-engineering baseline used to show DeDe's generality and as a warm-start initializer in the convergence experiment."},{"cited_title":"A Simple Effective Heuristic for Embedded Mixed-integer Quadratic Programming.In- ternational journal of control, 93(1):2–12, 2020","cited_arxiv_id":null,"evidence_quote":"Provides empirical evidence that ADMM iterates with projection handle mixed-integer quadratic programs."},{"cited_title":"Global Con- vergence of ADMM in Nonconvex Nonsmooth Opti- mization.Journal of Scientific Computing, 78:29–63, 2019","cited_arxiv_id":null,"evidence_quote":"One of the theoretical convergence results cited to support applying ADMM to non-convex problems."},{"cited_title":"lp-Box ADMM: A Versatile Framework for Integer Programming.IEEE transactions on pattern analysis and machine intelli- gence, 41(7):1695–1708, 2018","cited_arxiv_id":null,"evidence_quote":"One of the theoretical convergence results cited for ADMM with integer and boolean variables."},{"cited_title":"CVXPY: A Python- embedded modeling language for convex optimization","cited_arxiv_id":null,"evidence_quote":"The convex modeling language that DeDe's user interface and subproblem construction are built on."},{"cited_title":"Jordan, et al","cited_arxiv_id":null,"evidence_quote":"The parallel execution engine DeDe uses to run subproblems across CPU cores."}],"review_version":1}