{"id":"80f2afe3-c72b-403b-9667-2c429d8cb170","arxiv_id":"2411.14980","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Bivariate and trivariate polynomial coding schemes that support arbitrary matrix partitions reduce upload communication overheads relative to univariate codes for distributed matrix-matrix multiplication.","lead":"Distributed matrix multiplication can be sped up by assigning workers coded subtasks, but communication costs grow with how the matrices are partitioned. This paper extends multivariate polynomial codes to arbitrary partitions and shows in simulation that a trivariate scheme improves the latency versus communication trade-off.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section V violates the Rth≫N assumption behind upload overhead formulas (4)-(5), so the reported low-overhead latency comparison may be an artifact of under-counted upload costs.","rationale":"The algebraic core of the paper checks out: the recovery thresholds for the Bi0, Bi2, and Tri schemes are correctly derived, and the table entries are consistent with equations (2)-(5). The generalization of the bivariate schemes from [16] to arbitrary p1 is legitimate. The most load-bearing weakness is exactly the one identified by the reader: the upload overhead formulas are derived under Rth≫N, but the numerical section operates in a regime where Rth≤100 and N=300, so the approximation is invalid and the overhead constraints are too loose. Since the numerical comparison is the main evidence for the claimed trade-off improvement, this threatens the central quantitative claim, though not the existence of the schemes themselves. I considered whether the unproven 'lowest possible upload overhead' claim is a stronger concern, but it does not affect the correctness of the proposed schemes, only a marketing statement. No code or data is provided, so the simulation cannot be checked independently, but a competent group could re-implement it in weeks. The verdict should remain CONDITIONAL pending the finite-N recalculation.","tokens_in":9481,"tokens_out":13857,"duration_ms":131247,"concrete_test":"Re-run the Section V Monte Carlo optimization with exact finite-N upload overheads: for each (p0,p1,p2), set the number of required distinct product evaluations to max(Rth,N) (i.e., at least one subtask per worker), and compute R0 and R1 as the minimal Cartesian product sizes |X||Y| and |Y||Z| that yield that many evaluations while respecting the degree constraints |X|≥p0, |Z|≥p2, |Y|≥2p1−1. Use these R0,R1 in equations (4)-(5) and re-plot the latency-overhead curves of Figure 2. If the Tri scheme no longer strictly dominates the univariate scheme at low overhead constraints, the numerical claim is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II derives the upload overhead formulas (4)-(5) under the explicit assumption Rth ≫ N, counting only the inputs needed for Rth successful computations and neglecting the up to N−1 unfinished subtasks. Section V then optimizes over partitions with N=300, p0,p2≤10, and low overhead constraints that force p1=1, so Rth=p0p2≤100. The governing assumption is violated by a factor of at least 3 and up to 300. With finite N, keeping all workers busy requires at least max(Rth,N) distinct subtasks; the upload overheads in (4)-(5) are therefore underestimates. For p1=1, the exact overhead for the univariate scheme is δu,0 = p2−1+(N−1)/p0 (and symmetrically for δu,1), while for the Tri scheme, the Cartesian set must be expanded from X×Z to a product set of size at least N, adding upload on both sides. Because the univariate scheme is already penalized by the p2−1 and p0−1 terms, the extra finite-N term may affect the schemes differently and could change the reported ordering in Figure 2 at low overhead constraints. The paper neither reports the simulation scheduling protocol nor provides code, so it is impossible to tell whether the claimed advantage is robust. This is the central quantitative evidence for the trade-off improvement, so it is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies distributed matrix-matrix multiplication (MMM) under coded computing, extending the authors' previous bivariate polynomial codes to arbitrary matrix partitions (p0, p1, p2). The master partitions M0 into p0 x p1 blocks and M1 into p1 x p2 blocks, and assigns coded evaluations to N workers that compute multiple subtasks. The paper defines computation, upload, and download overheads relative to a single-server baseline, derives recovery thresholds and overhead expressions for a univariate entangled polynomial code (epc) and for two bivariate schemes (Bi0, Bi2) and one trivariate scheme (Tri) with Cartesian-product evaluation sets, and presents a Monte Carlo study of the latency-communication trade-off. The central claim is that the multivariate schemes achieve lower upload overhead than univariate codes, yielding new points in the latency-overhead trade-off.","tokens_in":9708,"tokens_out":14427,"duration_ms":127828,"significance":"If the claims are substantiated, the paper makes a useful incremental contribution to multivariate coded computing: it generalizes bivariate codes to p1 ≥ 1, introduces symmetric upload-overhead reduction in the Tri scheme, and correctly identifies that the penalty factors p0 - 1 and p2 - 1 in the univariate upload overhead can be removed at the cost of extra computation complexity. The algebraic derivations of Rth and the overhead expressions in Table I check out, and the tensor-product evaluation sets are unisolvent for the stated degree bounds, so the schemes are mathematically sound in the asymptotic regime Rth >> N. The paper is honest about the provenance of the tri-variate encoding polynomials from [6]. However, the numerical evaluation in Section V is not currently reliable, and the unsupported optimality claim should be corrected.","major_comments":[{"comment":"The upload overhead formulas (4)-(5) are derived under the explicit assumption Rth >> N, stated in Section II just before these equations. The numerical optimization in Section V, however, uses N = 300, p0, p2 ≤ 10, and at low overhead constraints the feasible regimes force p1 = 1, so Rth = p0 p2 ≤ 100 ≤ N. In this regime the neglected N - 1 unfinished subtasks are of the same order as or larger than Rth, so (4)-(5) underestimate the true upload cost. Because the univariate scheme carries additional p0 - 1 and p2 - 1 penalties, the reported ordering in Figure 2 at low overhead constraints may be an artifact of this under-counting. The authors should either restrict the search to partitions with Rth >> N, derive and use finite-N overhead expressions, or report the scheduling protocol and show that the conclusions are unchanged under exact accounting.","section":"Section II, Section V, Eqs. (4)-(5)"},{"comment":"The sentence 'The Cartesian product set guarantees decodability and provides the lowest possible upload communication overheads' asserts an optimality result without proof. Decodability is standard for tensor-product grids, but the 'lowest possible' part is a lower-bound claim over all evaluation sets and is not established. Since the paper's contribution is framed as new points in the trade-off, this unsupported claim should either be proved (e.g., via a cutset or rank argument on R0 and R1 for a given Rth) or replaced by a comparison with the univariate baseline. The current wording overstates what is shown.","section":"Section IV (before IV-A)"},{"comment":"The Monte Carlo evaluation of the latency T(p0, p1, p2) in (6) does not describe the subtask scheduling/assignment policy, the number of simulation runs, or the confidence intervals, and no code is released. Since Figure 2 is the primary quantitative evidence for the claimed trade-off improvement, these omissions prevent reproducibility and make it impossible to assess whether the scheme ordering is robust to finite-N effects. Please provide the simulation protocol and, preferably, code.","section":"Section V, Eq. (6)"}],"minor_comments":[{"comment":"In the paragraph defining δ, the text 'each partial computation ... involves r0/p0 r1/p1 r2/p1' should have the last denominator p2, not p1, to be consistent with the block dimensions and with (2).","section":"Section II (computation complexity)"},{"comment":"In the expressions for RBi0_0 and RBi0_1, 'RTri_th' appears to be a typo for 'RBi0_th'; as written, it equates two different recovery thresholds.","section":"Section IV-A"},{"comment":"Minor language issues: 'This encoding polynomials' should be 'These encoding polynomials', and 'witch' should be 'which'.","section":"Section IV-B"},{"comment":"Figure 2 lacks a clear statement of the range of δ̂u,d values and the number of Monte Carlo trials; consider adding error bars or stating that the reported curves are means over a fixed number of runs.","section":"Section V (Figure 2)"},{"comment":"The phrase 'For simplicity, we assume the number of partitions is large' could be made precise by stating a concrete inequality such as Rth ≥ cN for some constant c, and checking it for all simulated partitions.","section":"Section II"}],"recommendation":"major_revision","confidential_remarks":"The theoretical construction is sound, and the paper will likely be of interest to the coded computing community. The main risk is the numerical section: the authors should either fix the finite-N issue or substantially weaken the empirical claims. If they provide simulation details and an exact or corrected overhead analysis, a revised version could be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a legitimate, if modest, advance. The bivariate schemes Bi0/Bi2 are a direct generalization of the authors' earlier [16] from p1=1 to p1≥1, and the trivariate scheme, while using polynomials that appear in [6], is the first to evaluate them on a full Cartesian product set rather than along univariate curves. The recovery thresholds, overhead expressions, and the claim that the Cartesian product set is unisolvent for these multidegrees all check out; I re-derived them and agree. The trade-off formulation in Section II is clean and useful.\n\nThe soft spot is exactly the one the stress-test flags. Section II introduces upload overheads (4)-(5) under an explicit Rth≫N assumption, counting only the inputs needed for Rth successful computations and neglecting the up to N-1 unfinished subtasks. Section V then optimizes over partitions with N=300, p0,p2≤10, and at low overhead constraints p1=1, so Rth=p0p2≤100. That is not ≫N. When N exceeds the number of distinct subtasks, you cannot keep all workers busy with the nominal evaluation set; you need at least max(Rth,N) distinct subtasks, which changes the upload counts for every scheme. The paper does not report how the simulation handles this, and no code is provided. The under-counting affects the schemes differently, so the ordering in Figure 2 at low overhead is not reliable. I would trust the theoretical tables, but not the latency comparison as evidence for the claimed trade-off improvement.\n\nMinor points: the claim that the Cartesian product set 'provides the lowest possible upload communication overheads' is asserted without proof. It may be true among Cartesian sets, but as a global statement it is unproven. Also, the simulation protocol is under-specified (how subtasks are scheduled, how workers are assigned when N exceeds the number of subtasks, etc.).\n\nBottom line: the paper is a serious contribution for an ISIT-style venue; the theoretical results merit peer review. A good referee should push the authors to fix the numerical section or at least caveat that the overhead constraints are approximate in the low-overhead regime. I'd accept it for review, but I would not cite the latency comparison until it's corrected.","headline":"Solid incremental coded-computing paper with a real flaw in the numerical evaluation: the upload-overhead formulas are used outside their Rth≫N regime, so the reported latency gains may be overstated.","tokens_in":10298,"tokens_out":3411,"would_cite":false,"duration_ms":31256,"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":"A tri-variate polynomial code removes the upload-overhead penalties that univariate codes pay in distributed matrix multiplication, at the cost of more computation per block.","keywords":["distributed matrix-matrix multiplication","coded computing","polynomial codes","multivariate polynomial interpolation","straggler mitigation","communication overhead","upload cost","recovery threshold"],"falsifier":"Repeat the Section V latency comparison after replacing formulas (4)-(5) with exact upload counts for each $(p_0,p_1,p_2)$ configuration, e.g. simulating worker assignments until $R_{\\mathrm{th}}$ completed products arrive for $p_1=1$, $p_0=p_2=10$, $N=300$; if the exact univariate upload overhead is not $p_2-1$ (and $p_0-1$) times the single-server cost, the reported penalty and the latency gap between Tri and the univariate scheme are artifacts of the $R_{\\mathrm{th}}\\gg N$ approximation.","tokens_in":9281,"feed_emoji":"⚡","tokens_out":13274,"duration_ms":111799,"temperature":0.7,"pith_summary":"This paper extends bivariate polynomial codes for distributed matrix-matrix multiplication to support arbitrary matrix partitions $(p_0,p_1,p_2)$, going beyond the restricted partition that earlier multivariate schemes required. It proposes two families of coded computing schemes, one bivariate (Bi0 with its dual Bi2) and one tri-variate (Tri), and analyzes their computation-complexity and upload/download communication overheads relative to a single uncoded server. The central claim is that the Tri scheme brings both upload overheads down to $\\delta_{u,0}=\\delta_{u,1}=(p_1-1)/p_1$, eliminating the $p_0-1$ and $p_2-1$ penalties that univariate entangled polynomial codes incur, while the Bi0/Bi2 schemes remove the penalty on one of the two matrices. This matters because upload cost, not just computation, is a bottleneck in communication-constrained distributed systems, and the paper's latency simulations show Tri beating the univariate baseline under fixed overhead limits.","feed_headline":"Tri-variate code cuts upload cost in distributed matrix multiplication","feed_subtitle":"The new Tri scheme drops the p0 and p2 upload penalties of univariate codes at no extra download cost.","key_machinery":"The central object is the multivariate product polynomial built from the two encoded matrices, e.g. $\\tilde{M}^{\\mathrm{Tri}}(x,y,z)=\\tilde{M}_0^{\\mathrm{Tri}}(x,y)\\tilde{M}_1^{\\mathrm{Tri}}(y,z)$. The master chooses evaluation points on a Cartesian product $\\mathcal{X}\\times\\mathcal{Y}\\times\\mathcal{Z}$ rather than on a one-dimensional curve; this structured set guarantees decodability by multivariate polynomial interpolation and is what lets the paper count exactly how many coded blocks must be uploaded. The shared variable $y$ is the reuse mechanism: one evaluation of $\\tilde{M}_0(x,y)$ can be multiplied against up to $p_2$ evaluations of $\\tilde{M}_1(y,z)$ with the same $y$-coordinate, and one evaluation of $\\tilde{M}_1(y,z)$ against up to $p_0$ evaluations of $\\tilde{M}_0(x,y)$ with the same $y$-coordinate, reducing the number of distinct uploaded blocks. Bi0 and Bi2 use the same machinery with only one matrix encoded bivariately, giving an asymmetric upload saving.","core_discovery":"The paper claims that multivariate polynomial coding can be combined with arbitrary matrix partitions $(p_0,p_1,p_2)$ without paying the upload penalties that univariate entangled polynomial codes incur. In the bivariate scheme Bi0, the blocks of $M_0$ are encoded by $\\tilde{M}_0^{\\mathrm{Bi0}}(x,y)=\\sum_{b_0,b_1} M_0^{(b_0,b_1)} x^{b_0} y^{p_1-1-b_1}$ and those of $M_1$ by a univariate polynomial; because each evaluation $\\tilde{M}_1(y)$ is reused across $p_0$ values of $x$, the upload overhead on $M_1$ drops to $\\delta^{\\mathrm{Bi0}}=(p_1-1)/(p_1 p_2)$, while the overhead on $M_0$ remains $p_2-1+p_2\\delta^{\\mathrm{Bi0}}$. Bi2 is the dual scheme obtained by swapping $p_0$ and $p_2$. In the tri-variate scheme Tri, $\\tilde{M}_0^{\\mathrm{Tri}}(x,y)=\\sum_{b_0,b_1}M_0^{(b_0,b_1)}x^{b_0}y^{b_1}$ and $\\tilde{M}_1^{\\mathrm{Tri}}(y,z)=\\sum_{b_1,b_2}M_1^{(p_1-1-b_1,b_2)}y^{b_1}z^{b_2}$, so the target block $M^{n_0,n_2}$ is the coefficient of $x^{n_0}y^{p_1-1}z^{n_2}$ in the product polynomial. With the Cartesian product evaluation set $\\mathcal{X}\\times\\mathcal{Y}\\times\\mathcal{Z}$, $|\\mathcal{X}|=p_0$, $|\\mathcal{Y}|=2p_1-1$, $|\\mathcal{Z}|=p_2$, recovery needs $R_{\\mathrm{th}}=p_0p_2(2p_1-1)$ evaluations, and the upload overheads for both matrices become $\\delta_{u,0}=\\delta_{u,1}=(p_1-1)/p_1$. Simulations with 300 workers and shifted-exponential task times show Tri with the lowest average latency under equal upload/download constraints, while the univariate scheme is, in the paper's words, \"heavily penalized\" at low communication overheads.","pith_inferences":["The same shared-$y$ reuse mechanism should carry over to matrix-chain products and to secure distributed matrix multiplication, where upload and storage costs are also limiting; the paper does not analyze those settings.","The paper assumes a broadcast uplink, where uploading one coded block reaches all workers; in a unicast or star network the reuse of evaluations would not reduce total traffic by the same factor, so the ranking of schemes could change.","A boundary test worth running is the regime where $R_{\\mathrm{th}}$ approaches $N$; the paper's upload-overhead formulas are derived for $R_{\\mathrm{th}}\\gg N$, so exact counting at, say, $p_1=1$, $p_0=p_2=10$, $N=300$ would show whether the reported low-overhead advantage of Tri is robust."],"forward_implications":["If Tri works as described, choosing finer partitions in the $p_0$ and $p_2$ dimensions no longer increases either upload overhead; both stay at $\\delta_{u,0}=\\delta_{u,1}=(p_1-1)/p_1$.","Bi0 and Bi2 give asymmetric intermediate trade-offs: Bi0 multiplies the computation-complexity overhead by $p_0$ relative to the univariate scheme and removes the upload penalty on $M_1$, while Bi2 multiplies it by $p_2$ and removes the upload penalty on $M_0$.","Under the paper's shifted-exponential model with 300 workers, Tri achieves the lowest average latency among the schemes considered for the tested communication-overhead constraints.","The three schemes have recovery thresholds that remain linear in the partition level $K=p_0p_1p_2$: $p_0(p_2p_1+p_1-1)$ for Bi0, $p_2(p_0p_1+p_1-1)$ for Bi2, and $p_0p_2(2p_1-1)$ for Tri."],"supporting_citations":[{"why":"introduces the bivariate polynomial coding scheme (for p1=1) that this paper generalizes to arbitrary matrix partitions; supplies the upload-efficiency baseline.","marker":"[16]"},{"why":"defines entangled polynomial codes, the univariate baseline whose generalized multiple-subtask version is characterized in Section III and compared against.","marker":"[5]"},{"why":"introduces generalized PolyDot codes and the underlying tri-variate encoding that this paper evaluates on a Cartesian product set rather than a one-dimensional curve.","marker":"[6]"},{"why":"provides the shifted-exponential task-completion model used in the Monte Carlo latency simulations of Section V.","marker":"[19]"}],"fun_headline_variants":["Tri scheme slashes upload cost in distributed matrix multiplication","Generalized multivariate codes improve latency for distributed matrix multiply","Tri-variate code reduces upload overhead for two-matrix distributed computation","Multivariate codes with arbitrary partitions cut communication cost","Tri scheme outperforms univariate in distributed matrix multiplication trade-off"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that upload cost can be counted by the number of distinct coded blocks sent to the workers over the whole computation, which requires the recovery threshold to be much larger than the number of workers ($R_{\\mathrm{th}}\\gg N$); the paper's own Section V search includes low-overhead cases with $p_1=1$ and $R_{\\mathrm{th}}=p_0p_2\\le 100$ while $N=300$, a regime where that premise is violated.","fun_headline_variants_meta":{"raw":{"variants":["Tri scheme slashes upload cost in distributed matrix multiplication","Generalized multivariate codes improve latency for distributed matrix multiply","Tri-variate code reduces upload overhead for two-matrix distributed computation","Multivariate codes with arbitrary partitions cut communication cost","Tri scheme outperforms univariate in distributed matrix multiplication trade-off"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000529,"raw_usage":{"total_tokens":2694,"prompt_tokens":1233,"completion_tokens":1461,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":849,"completion_tokens_details":{"reasoning_tokens":1381}},"tokens_in":849,"tokens_out":1461,"duration_ms":11491,"temperature":1.0,"reasoning_tokens":1381,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:39:00.527763+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Repeat the Section V latency comparison after replacing formulas (4)-(5) with exact upload counts for each $(p_0,p_1,p_2)$ configuration, e.g. simulating worker assignments until $R_{\\mathrm{th}}$ completed products arrive for $p_1=1$, $p_0=p_2=10$, $N=300$; if the exact univariate upload overhead is not $p_2-1$ (and $p_0-1$) times the single-server cost, the reported penalty and the latency gap between Tri and the univariate scheme are artifacts of the $R_{\\mathrm{th}}\\gg N$ approximation.","supporting_citations":[{"cited_title":"Bivariate polyno- mial coding for efficient distributed matrix multiplication,","cited_arxiv_id":null,"evidence_quote":"introduces the bivariate polynomial coding scheme (for p1=1) that this paper generalizes to arbitrary matrix partitions; supplies the upload-efficiency baseline."},{"cited_title":"Straggler mitigation in distributed matrix multiplication: Funda- mental limits and optimal coding,","cited_arxiv_id":null,"evidence_quote":"defines entangled polynomial codes, the univariate baseline whose generalized multiple-subtask version is characterized in Section III and compared against."},{"cited_title":"On the optimal recovery threshold of coded matrix multiplication,","cited_arxiv_id":null,"evidence_quote":"introduces generalized PolyDot codes and the underlying tri-variate encoding that this paper evaluates on a Cartesian product set rather than a one-dimensional curve."},{"cited_title":"Tofec: Achieving optimal throughput-delay trade-off of cloud storage using erasure codes,","cited_arxiv_id":null,"evidence_quote":"provides the shifted-exponential task-completion model used in the Monte Carlo latency simulations of Section V."}],"review_version":1}